浮生若梦_Y

未归档

专题训练(1)

/ 注册

全部文章 / 未归档（共3篇）

RMQ问题的求解方法—ST算法

ST算法针对的是没有修改操作的多次询问的RMQ问题，如果遇见动态的RMQ问题，使用时要谨慎。主要思路：dp 预处理时间复杂度：预处理时间复杂度O（nlogn），查询时间O（1）。我们还是直接题目引入：输入一串数字，给你 ...

2019-08-06

0 408

离散化树状数组求逆序对

离散化树状数组求逆序对今天在学校 o j oj oj上看见一道求逆序对的题，上一次企图用...

2019-08-06

0 538

树状数组的基本操作

一、单点修改，区间查询题目描述：给出一个长度为n的序列，有m个操作，分别为询问[l,r]的区间和，和将x位置上的值增加C。思路：可以使用线性数组进行操作，对于每一次询问，修改的时间复杂度为O(1)，询问的时间复杂度为O(n)。如果数量n较大，这种操作必定会超时，所以我们尝试用前缀和来...

树状数组

2019-07-25

0 427