重链剖分

xiezheyuan · 2023-07-14 16:30:30 · 算法·理论

前言

轻重链剖分可以在 O(n) 的时间复杂度预处理一棵树，然后可以：

比如说上面这个树中，我们可以从根节点 1 开始，按照 DFS 被访问到的顺序来遍历，我们称每个点被访问到的次序为 DFS 序，如上图中的 dfn（显然，DFS 序是有很多种的

DFS 序的特点是，一个子树中的所有点在 DFS 序上正好对应一个连续区间，因此我们可以用线段树之类的高效的维护子树信息。小练习。

但是如果我们要维护链信息，那么朴素的 DFS 序就不方便了。因为似乎不是连续的。

且慢——比如说 6\to 7,6\to 9 等的短链 DFS 序就是连续的。但是长的链仍然需要拆成很多个短链。我们发现，DFS 序的连续取决于你访问是否连续，于是我们想到，是不是可以将比较重要的儿子先访问

引入概念：我们称一个非叶子节点的子节点中，子树大小最大的子节点称为这个节点的重子节点。比如说，上图中轮廓加粗了的点就是其父节点的重子节点，而其它子节点称之为轻子节点。此外，从父节点连向子节点的边，若连向重子节点，则为重边，否则为轻边。

于是我们可以考虑对于每一个节点，一律考虑先访问它的重子节点，其它节点随意。这时得到了新的 DFS 序，如上图中的 seg（显然，这种 DFS 序也是有很多种的）。

可以发现，这样子 DFS 序连续的链就比较长了，比如说 1 \to 2 \to 6 \to 7。对于这样 DFS 序连续的链，就是除深度最小的节点外其它节点均为某一个节点的重子节点所组成的链，我们称之为重链，如上图的红色链所示。这种方法我们称为重链剖分。

这样显然是很有优势的。但是具体有什么优势呢？

定理：任意一个节点 i 的轻子节点的子树大小不超过 i 的子树大小的一半。

Proof：反证法，如果超过了一半，则不存在其它子节点的子树大小比它大，所以这个节点应为重子节点，与前矛盾。

引理：从根节点到任意节点的路径上，轻边数量不超过 \log_2 n 。

Proof：令根节点到节点 i 的轻边数为 a，i 的子树大小为 b。

每过一条轻边，子树大小都将至少减半（如果不减半必定连接的不是轻子节点）。于是 b\leq\dfrac{n}{2^a}。

又因为 b\geq1，所以 n\leq 2^{a}，所以 a\leq \log_{2}n。证毕。

推论：从根节点到任意节点的路径上，重链数量不超过 \log_2 n。

Proof：每经过一条轻边，意味一条重链的结束，所以重链数量与轻边数量同级。

结论：任意两点之间的重链数量和轻边数量均不超过 O(\log n) 级别。

首先讨论如何求得重链剖分的 DFS 序和每条重链（实际上只需要保存每个节点所在链的链顶）。

首先第一遍 DFS，找到每个非叶子节点的重子节点。

然后第二遍 DFS，先遍历重子节点，然后遍历其它轻子节点，遍历轻子节点时新开一条重链。重子节点继承其父亲的重链。

对于链修改，首先判断左右节点是否在同一个重链上，如果在，直接搞，否则让左右节点中所在重链顶深度较小的那个点跳到重链顶，中途修改跳过的点的信息，最后令其跳到它的父节点）。直到两个节点位于同一条重链。

链修改同理。

练习1 | 练习2| 练习3

有些题（比如说这道题）维护的是边权，而朴素的重链剖分只能维护点权。我们可以将边权转化为边所连接的两点中深度较大的一点的点权。

树上 k 级祖先：这道题我们可以预先求得一点的 k 级祖先深度，然后跳重链，跳到链顶小于等于期望的深度。此时答案在这条重链里，可以 O(1) 求。

喷泉：这道题第一部分是一个单调栈不讲。然后跳重链时减去容积。直到容积小于等于 0，此时答案在重链里，可以在重链中二分求解，具体可以看我的题解。