Data Struct
Data Struct
单点修改，区间查询,\(1 \le n,q \le 2 \times 10^5\)
我是普及组选手，我会暴力
\(O(1)-O(n)\)
我是普及组一等选手，我会维护前缀和
\(O(n)-O(1)\)
我是提高组选手，我会一个\(Trick\):
把数组分成一块一块，维护每一块的和，对于单点修改，修改两个即可，区间查询可以将一些整块的和直接贡献答案，剩下的直接一个一个读
时间为:
其中B为块长
取\(B=\sqrt{n}\),则时间为\(O(\sqrt{n}q)\)
这个Trick，我取名为分块
我是笔者，我告诉更快的方法
多层分块，选层数为\(\log_2 n\), 块长为\(2\)，时间为\(O(\log_2 n)\)
线段树诞生了!!!
区间修改，区间查询
懒标记lazy_tag,那么直接和区间查询一样了，有些不用向下递归了
区间查询或不是整块的，直接下传。
区间加，区间乘法，区间查询
设计lazy_tag
尝试跟上方一样，只用一个tag, 但会单次为线性
合并+,x,最后将操作序列变成为:
\(\times + \times + ...\)
我们证明可以将以上操作可以变成\(\times +\),那么保证了时间复杂度
如此下来，我们考虑上线段树，必须考虑合并过程。
那么我们考虑群，将集合\((G,+)\)，其中G为线段树要维护的东西，+是合并过程
合并的操作必须满足G+G $\longrightarrow $ G
这个集合明显是一个半群，那么就是半群
课后习题:P5609(考虑线段树维护函数)
我们上面已经说明，答案的合并和答案的类型构成双半群
修改D和合并+操作要满足结合律，那么\((D,+)\)是半群。
修改合并满足:\(D+D \longrightarrow D\)
那么线段树有双半群结构
修改和信息必须满足分配律，如:
而且合并\(\times\)需要满足：
\(D \times G \longrightarrow G\)
线段树的时间复杂度非\(O(q\log n)\), 而是：
因为我们以前的所有的时间复杂度为\(O(q\log n)\)，只是因为他们是O(1)
可持久化线段树/主席树
集合查询kth大
考虑建值域线段树，则可以直接二分，时间复杂度\(O(n\log n)\)
静态 区间查询第k大
考虑[l,r]中的值域线段树，可以直接暴力，时空复杂度为\(O(n^2\log n)\),不可接受
考虑线段树减法，我们不维护[l,r]的值域线段树，转而维护前缀的值域线段树,可以动态开点,此线段树名为主席树/可持久化线段树
或者对于所有询问进行二分，时间复杂度为\(O(n\log^2 n)\)
静态区间查询mex
值域线段树中第一个为0的数，上可持久化树即可
CDQ分治
CDQ提出CDQ分治
注意:CDQ分治是离线算法
动态二维偏序
等同于三维偏序
先离线下来，然后按时间排序，然后假设已经弄出了左儿子的答案，然后计算左儿子对右边影响，最后我们递归下去，计算左，右的答案即可
优化dp
当转移方程为:
三维偏序，用CDQ分治
CDQ分治的思想准确来说是用一个\(\log\)的时间，消掉一个操作即可
三维偏序其他做法
(1) 只求数量
用bitset乱搞，时间为\(O(\frac{3n^2}{w})\)
如果是k维偏序， 则时间为\(O(\frac{kn^2}{w})\), 时间大大超过CDQ分治
(2) K-D Tree
将在K-D Tree给出
(3) 树套树
没必要讲，DS中的暴力，笔者看不起
整体二分
整体二分解决一类“多次二分答案”的问题。
例如有 \(q\) 个询问，每个询问都是“求第 \(k\) 大”，如果对每个询问单独二分，答案是 \(O(q \log n)\) 次 check，每次都扫一遍序列，太慢。
整体二分把所有询问一起二分。
具体来说，定义函数 solve(l, r, qlist) 表示当前处理到的答案范围是 \([l,r]\)，需要回答的询问集合是 qlist。
每次取 \(mid = \frac{l+r}{2}\)，把当前所有修改中小于等于 \(mid\) 的加到数据结构里，然后判断每个询问的答案是在 \([l,mid]\) 还是 \([mid+1,r]\)，分到两边递归。
数据结构通常用树状数组清空。
经典题：动态区间第 k 大（洛谷 P2617 Dynamic Rankings）。
有修改，有查询，整体二分可以做到 \(O((n+q) \log^2 n)\)。
整体二分和 CDQ 分治很像，区别在于 CDQ 是消去时间维度，整体二分是消去值域维度。
树套树
线段树套平衡树：外层下标线段树，内层平衡树。支持区间查询排名、前驱后继等，\(O(\log^2 n)\)。
树状数组套主席树：解决动态区间第 k 大，相比整体二分，可以强制在线。
线段树套线段树：二维数点问题，空间通常要动态开点。