线段树分治总结

_Luminous · 2025-02-04 16:39:26 · 算法·理论

看到什么应该想到线段树分治？

• 多个操作，每一个操作的影响范围是一个区间（时间区间，询问区间）。
• 多个询问，询问（某个时间时，某个操作后的）答案。

线段树分治的思想

对时间（询问）建立一棵线段树，树的节点存的信息是覆盖了这个区间的操作。

考虑遍历整棵线段树，维护一个可撤销并查集。当进入一个线段树的子节点时，在并查集上添加覆盖这个区间的边。然后继续地归子节点，直到叶子节点（对应的就是一个询问），统计对应的答案。回溯时，将这个节点加的边在并查集上撤销。

这样，递归到每一个叶子节点时，并查集中的边都是这个询问的完整状态。

分析复杂度，遍历线段树的时间是 O(n\log n) 的，总共 O(n) 个操作，每一个操作在线段树上最多覆盖 \log n 个节点，可撤销并查集由于不能使用路径压缩，所以按秩合并，复杂度是 O(\log n) 的。维护操作的复杂度是 O(n \log^2 n) 的。

按秩合并：为每一个节点维护一个秩，表示以该节点为根的树的高度的上界。合并时，以秩小的根指向秩大的节点。

相关 dsu

扩展域并查集

有很多形式。

• 维护二分图：

  考虑对于每一个真实的点，建立反点，并查集上点 x 和点 y 的反点连一条边，意思是点 x 不能和点 y 在二分图的同一个部。

  真实的图中连一条边，说明两个点不能在一个部中，这时分别给对方的反点在并查集上连边，完成操作。

  如果一次操作连接点 x 和点 y，但是并查集中 x 和 y 在一个树中，就不是二分图。

可撤销并查集

考虑并查集操作：把 x 指向 y，操作前 x,y 都是根节点，撤销一次操作就是把 x 指向自己。

撤销需要按操作的顺序来，也就是说需要用栈将进行的操作存下来，需要撤销的时候直接弹栈，令 fa_x\leftarrow x 即可。