重链剖分
xiezheyuan · · 算法·理论
前言
轻重链剖分可以在
-
-
-
-
- 只想到了这么多
DFS 序与重链剖分
比如说上面这个树中,我们可以从根节点
DFS 序的特点是,一个子树中的所有点在 DFS 序上正好对应一个连续区间,因此我们可以用线段树之类的高效的维护子树信息。小练习。
但是如果我们要维护链信息,那么朴素的 DFS 序就不方便了。因为似乎不是连续的。
且慢——比如说
引入概念:我们称一个非叶子节点的子节点中,子树大小最大的子节点称为这个节点的重子节点。比如说,上图中轮廓加粗了的点就是其父节点的重子节点,而其它子节点称之为轻子节点。此外,从父节点连向子节点的边,若连向重子节点,则为重边,否则为轻边。
于是我们可以考虑对于每一个节点,一律考虑先访问它的重子节点,其它节点随意。这时得到了新的 DFS 序,如上图中的 seg(显然,这种 DFS 序也是有很多种的)。
可以发现,这样子 DFS 序连续的链就比较长了,比如说
这样显然是很有优势的。但是具体有什么优势呢?
重链剖分的时间复杂度证明
定理:任意一个节点
Proof:反证法,如果超过了一半,则不存在其它子节点的子树大小比它大,所以这个节点应为重子节点,与前矛盾。
引理:从根节点到任意节点的路径上,轻边数量不超过
Proof:令根节点到节点
每过一条轻边,子树大小都将至少减半(如果不减半必定连接的不是轻子节点)。于是
又因为
推论:从根节点到任意节点的路径上,重链数量不超过
Proof:每经过一条轻边,意味一条重链的结束,所以重链数量与轻边数量同级。
结论:任意两点之间的重链数量和轻边数量均不超过
具体维护方法
常规维护方法
首先讨论如何求得重链剖分的 DFS 序和每条重链(实际上只需要保存每个节点所在链的链顶)。
首先第一遍 DFS,找到每个非叶子节点的重子节点。
然后第二遍 DFS,先遍历重子节点,然后遍历其它轻子节点,遍历轻子节点时新开一条重链。重子节点继承其父亲的重链。
对于链修改,首先判断左右节点是否在同一个重链上,如果在,直接搞,否则让左右节点中所在重链顶深度较小的那个点跳到重链顶,中途修改跳过的点的信息,最后令其跳到它的父节点)。直到两个节点位于同一条重链。
链修改同理。
练习1 | 练习2| 练习3
边权的维护
有些题(比如说 这道题)维护的是边权,而朴素的重链剖分只能维护点权。我们可以将边权转化为边所连接的两点中深度较大的一点的点权。
根到点的特殊路径信息维护
树上 k 级祖先 :这道题我们可以预先求得一点的
喷泉:这道题第一部分是一个单调栈不讲。然后跳重链时减去容积。直到容积小于等于