这篇会理论上讲一讲常用的数据结构维护手法。

我是嘴巴选手我自豪！

①cdq分治

现在我们有一些修改，有一些询问，修改之间独立。

我们考虑分治，对于左右两半分别分治，然后对于左边的修改计算对右边询问的贡献。

本身的复杂度是O(nlogn)。

②整体二分

现在我们有一些修改，有一些询问。

我们需要求出，在最少多少组修改之后满足题目条件。（或者可以转化成这样）

对于单组询问，我会二分！对于多组询问，真不巧，二分超时了...

我们考虑整体二分。整体二分的框架大概是这样：

def 整体二分(el,er,ql,qr):    if el==er:        ql到qr的答案都是el        return     em=(el+er)/2    模拟el...em的操作    看一下ql...qr哪些满足了    满足的放到ql...qm，不满足的放到qm+1...qr    整体二分(em+1,er,qm+1,qr)    撤销el...em的操作    整体二分(el,em,ql,qm)

本身的复杂度是O(nlogn)的。

③时间倒流

现在我们有一些修改（例如删除边啥的），有一些询问。

修改反着做比正着做容易。

既然可以离线，干脆把修改倒过来做。

④根号重构

现在我们有一些修改，有一些询问，修改之间独立。

对于一堆修改计算对一堆询问的贡献复杂度比较高（例如和询问修改个数无关，而和其它东西有关），而单个修改对单个询问贡献复杂度很低。

同时我们可以用相对比较低的复杂度把一坨修改预处理一波，计算预处理之后的东西对单个询问贡献复杂度很低。

我们可以每根号个修改预处理一次，然后询问就枚举还没预处理的修改以及预处理好的算贡献就可以了。

本身的复杂度是O(n√n)。

⑤莫队

现在我们没有修改，只有一大堆询问。

询问十分复杂，但是如果知道了[l,r]的答案，可以很快得到[l,r-1]和[l,r+1]和[l-1,r]和[l+1,r]的答案。

考虑把l分成根号块，把所有询问排序，按l所在的块编号为第一关键字，r为第二关键字排序，暴力拓展当前的区间。

本身的复杂度是O(n√n)。

⑥线段树分治

现在我们有一些区间修改，有一些单点询问，询问在所有修改之后。

比较容易支持对当前状态进行修改，并撤销这次修改（如果不再进行其它修改）。

考虑对于区间建出线段树结构（只要结构），然后对于每个修改下放到log个区间，然后我们在线段树上分治，进这个点的时候进行这个点所有修改，出这个点的时候撤销这些修改，对于叶节点记录一下答案。

本身的复杂度是O(nlogn)。

⑦二进制分组

现在我们有一些修改，有一些询问，修改之间独立。强制在线。

我们可以以一个与修改个数有关的时间预处理出一些修改的信息，对于一个询问可以快速地在预处理后的一些修改中获取信息。

我们可以采用二进制分组的思想，感觉这种做法只能看图了...

本身的复杂度是O(nlogn)。

（遇到新的再更新qaq）

一些常用的数据结构维护手法