思想

线段树分治是线段树的一种高级技巧，简单来说，就是用线段树结构，将所有询问区间分解为 $O(\log)$ 个整块，并离线记录到相应节点，询问结束后遍历一遍整棵树，递归求解或直接求解出每一个节点的答案。

例题 $\mathrm{I}$

维护一个异或线性基，支持以下操作：

• 加入一个正整数 $x(x < 2^{31})$；
• 删除第 $k$ 个加入的元素；
• 每次操作结束后，求出当前线性基的最大异或值。

要求维护一个可撤销线性基，我们考虑如何用线段树分治。

对于时间轴建立线段树，每一个点代表一段时间。

将加入看作是在一段区间上进行插入操作，然后是用线段树分成 $O(\log n)$ 个小段，离线标记。

最后遍历整颗线段树，对于每一个树上节点求出答案，于是我们将删除操作变为了递归时的撤销操作，复杂度 $O(n\log^2 n)$。

以上就是将某个数据结构变为可撤销的线段树分治做法，复杂度上有 $O(\log n)$ 的代价。

例题 $\mathrm{II}$

咕