树链剖分

概念

树链剖分是一种将树分割成若干条链的形式，以维护树上路径的信息的方式。

树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作 实链剖分），大多数情况下（没有特别说明时），树链剖分 都指 重链剖分。

重链剖分可以将树上的任意一条路径划分成不超过 $\log n$ 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。

重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。

如：路径修改、路径查询、子树修改、子树查询等。

时间复杂度通常能达到 $O(\log^2 n)$ 甚至结合高级数据结构达到 $O(\log n)$。

除了配合数据结构来维护树上路径信息，树剖还可以用来 $O(\log n)$ 求 LCA（常数较小）。在某些题目中，还可以利用其性质来灵活地运用树剖。

下面给出一些定义：

• 重儿子：对于一个节点 u，它的子节点中子树大小最大的那个子节点被称为 u 的重儿子（如果有多个大小相同，任选一个）。u 与它的重儿子之间的边称为**重边。
• 轻儿子：u 的其他子节点称为轻儿子。u 与轻儿子之间的边称为**轻边。
• 重链：由连续的重边连接而成的路径称为一条重链。
• 轻边：连接不同重链的桥梁。
• 链头：每条重链的顶端节点（链中深度最小的节点）。

性质

关键性质：从树根到任意一个叶子节点的路径上，遇到的轻边数量不超过 O(log n) 条。

证明（直观理解）：考虑从根节点 root 走到叶子节点 leaf。
每经过一条轻边 (parent -> child)，意味着 child 不是 parent 的重儿子。
根据重儿子的定义，child 的子树大小 size[child] <= size[parent] / 2（因为重儿子的子树大小至少占一半）。
子树大小每次经过轻边至少减半！树的大小 n 最多能减半 O(log n) 次（从 n 减到 1），所以轻边的数量最多是 O(log n)。
推论：因为一条路径 u -> v 可以看作 u -> LCA(u, v) 和 LCA(u, v) -> v 两条路径的拼接，每条路径最多有 O(log n) 条轻边，那么整条路径最多被拆分成 O(log n) 段重链（因为轻边连接着重链，经过 O(log n) 条轻边就意味着要经过 O(log n) 条重链）。