线段树分治

作用

线段树通过维护序列，可以维护一个承载各种操作的时间轴。

通常用于辅助一些不支持删除操作的数据结构（线性基，并查集），
这种情况可以用线段树分治维护操作影响的时间来巧妙地避开删除。

线段树结构

线段树分治用到的线段树（以下简称线段树）是以询问的时间为键值，
没有权值只有标记的线段树。

也就是线段树的一段区间对应的是一段询问（一段时间）。

这样的线段树只需要支持区间修改（打标记）。
每一个操作都会影响一段时间，对应于线段树的区间修改。

例题

这玩意需要一个例题才讲的清。
（由于线段树分治用于辅助其他数据结构，再看例题前得先会线性基）

维护一个集合，每次操作可以加入一个数或删除一个已经存在与集合的数。
每次操作后要回答这个集合的最大异或和。
操作次数 1e5 。

暴力线性基

如果只有插入没有删除，这题就是一遍线性基。

但是不巧线性基不支持删除，所以只能在每次删除后重构线性基。
复杂度平方带对数，稳 T 。

时间轴

将每次操作看做时间点，假设数 x 在时刻 l 被插入， r 被删除，
那么 x 只存在于 [l, r) 这段时间，
假如每个时刻开一个线性基，那么将 x 插入 [l, r) 的每个线性基，
这样就可以在最后通过线性基询问得到每个时刻的答案，
复杂度还是平方带对数，稳 T 的离线算法。

线段树优化

比较上述两种算法，
第一种复杂度瓶颈在于重构线性基，实在是没有什么优化空间，
但是第二种算法中，复杂度瓶颈在于将 x 插入到 [l, r) 的每个线性基，
这个操作相当于一个区间修改，可以用线段树优化。

那么一个优秀的算法就出来了：
线段树每个节点维护一个 vector （相当于懒标记），插入 x 将直接加在线段树对应区间的 vector　内。
所有操作过后会得到一个只有懒标记的线段树，
然后考虑如何通过这样一颗线段树得出所有答案。

处理懒标记

懒标记下传？
不存在的，因为懒标记是一个 vector, 下传的复杂度并不是 O(1) ，
不难验证下传所有懒标记会使复杂度重回 n 方。

既然不能下传，那就进行 n 次单点查询？
一个道理，单点查询的复杂度并不是 log(n), 这样做同样对复杂度没有优化。

那就没救了

分治

线段树分治，不能只有线段树，还要分治啊。

现在需要只把每个懒标记访问一遍就得出所有答案。

dfs 整颗线段树（实际上就是分治），深度是 log 级别的，那么对每一个深度开一个线性基。
如能能让 dfs 每个节点时该深度线性基维护的是这个节点到根的所有懒标记，
最后 dfs 到每个叶子节点就可以得到该叶子节点到根的懒标记的线性基，也就可以求出这个叶子节点的答案。

假设当前 dfs 到 u, 深度为 d, 深度对应的线性基已经是维护其到根的懒标记。
dfs 到一个新点 v 一定会使深度 + 1 ，将当前深度 d 的线性基拷贝到下个深度 d + 1 中。
那么 dfs 到 v 后再将 v 的懒标记加到 d + 1 的线性基中，d + 1 的线性基也就满足了要求。
通过这样的过程就能够做到只访问每个懒标记一遍。

这就是线段树分治了。

真 - 例题

这两道题就没有这么裸了。

洛谷八纵八横 （线段树分治 + 线性基）

BZOJ 二分图 （线段树分治 + 并查集）