1. 树链剖分与重链剖分概述树链剖分Tree Chain Partition是一种将树形结构分解为若干线性链的算法技术而重链剖分Heavy-Light Decomposition则是其中最经典和实用的实现方式。我第一次接触这个算法是在解决一道树上路径查询问题时当时就被它化树为链的巧妙思路所震撼。简单来说重链剖分通过特定的规则将树分解为多条链使得从根节点到任意节点的路径最多经过O(log n)条链。这种特性使得我们能够将许多树上的操作转化为对线性序列的操作从而可以套用线段树、树状数组等成熟的数据结构进行处理。在实际应用中重链剖分最常见的用途包括但不限于树上路径的区间查询/修改子树整体操作LCA最近公共祖先的高效求解结合其他数据结构维护动态树信息提示虽然树链剖分有多种变体如长链剖分、虚实链剖分等但在算法竞赛和工程实践中除非特别说明否则树链剖分默认指的就是重链剖分。2. 重链剖分的核心原理2.1 基本概念定义理解重链剖分需要先掌握几个关键概念重儿子Heavy Child对于非叶子节点其子树大小最大的子节点称为重儿子。如果有多个子节点子树大小相同可任选其一。轻儿子Light Child除重儿子外的其他子节点。重边Heavy Edge连接节点与其重儿子的边。轻边Light Edge连接节点与其轻儿子的边。重链Heavy Path由连续的重边组成的极长路径。通过这样的定义整棵树就被分解为了若干条重链其间由轻边连接。下图展示了一个分解示例注实际文章中应配图A ├── B (重) │ ├── D (重) │ │ └── H │ └── E └── C ├── F └── G (重) └── I重链A-B-D-HG-I其余为轻边2.2 关键性质证明重链剖分的威力来自于以下两个关键性质性质1从根节点到任意节点的路径上经过的轻边数量不超过O(log n)证明思路考虑从当前节点向上跳一条轻边时子树大小至少翻倍因为父节点选择了更大的子树作为重儿子因此最多跳log n次就会到达根节点。性质2任意路径可以被划分为O(log n)条重链的连续部分这直接由性质1衍生而来因为两条重链之间必然由轻边连接。这些性质保证了基于重链剖分的算法通常具有O(log n)的单次操作时间复杂度假设使用O(log n)的数据结构维护链信息。3. 重链剖分的实现细节3.1 预处理步骤详解实现重链剖分需要两次DFS遍历第一次DFS计算子树大小(size)、确定重儿子(son)void dfs1(int u, int fa) { size[u] 1; for (int v : tree[u]) { if (v fa) continue; dfs1(v, u); size[u] size[v]; if (size[v] size[son[u]]) son[u] v; // 更新重儿子 } }第二次DFS进行链式分解记录节点在DFS序中的位置(dfn)所在链的顶端节点(top)DFS序对应的原始节点(rev)void dfs2(int u, int tp) { top[u] tp; dfn[u] cnt; rev[cnt] u; if (son[u]) dfs2(son[u], tp); // 优先处理重儿子 for (int v : tree[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子开启新链 } }注意在实际编码中通常还需要记录父节点(fa)和深度(dep)信息这些在后续操作中会用到。3.2 数据结构的选择与实现重链剖分通常需要配合区间数据结构使用线段树是最常见的选择struct SegmentTree { struct Node { int l, r; int sum, tag; } tr[N2]; void pushup(int u) { tr[u].sum tr[u1].sum tr[u1|1].sum; } void build(int u, int l, int r) { tr[u] {l, r}; if (l r) { tr[u].sum val[rev[l]]; // 注意rev映射 return; } int mid (l r) 1; build(u1, l, mid); build(u1|1, mid1, r); pushup(u); } // 省略update和query实现 };实际应用中根据问题需求可能需要实现不同的区间操作如区间加、区间乘、区间最值等。4. 典型操作实现4.1 路径查询/修改这是重链剖分最核心的操作基本思路是将路径拆分为若干重链区间分别处理int query_path(int u, int v) { int res 0; while (top[u] ! top[v]) { // 不断将u和v向链顶跳 if (dep[top[u]] dep[top[v]]) swap(u, v); res seg.query(1, dfn[top[u]], dfn[u]); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); res seg.query(1, dfn[u], dfn[v]); return res; }修改操作与查询类似只需将查询函数替换为更新函数即可。4.2 子树查询/修改由于DFS序的连续性子树操作反而更加简单int query_subtree(int u) { return seg.query(1, dfn[u], dfn[u] size[u] - 1); }4.3 LCA查询虽然重链剖分不是求LCA的最高效算法但实现起来非常直观int lca(int u, int v) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) u fa[top[u]]; else v fa[top[v]]; } return dep[u] dep[v] ? u : v; }5. 实战技巧与优化5.1 常见错误排查DFS序映射错误最容易出错的地方是忘记在构建线段树时使用rev[dfn]进行值映射导致访问了错误的节点值。边界条件处理在路径操作中当u和v位于同一条链时需要确保dfn[u] ≤ dfn[v]。轻边遗漏在dfs2中容易忘记处理非重儿子的情况导致链分解不完整。5.2 性能优化技巧使用BFS替代DFS对于特别深的树可以改用非递归的BFS实现避免栈溢出。内存访问优化将dfn、rev等数组连续存储提高缓存命中率。数据结构选择对于只有单点修改的问题可以用树状数组替代线段树对于子树操作多的问题可以考虑使用前缀和。并行预处理在允许的情况下可以将两次DFS合并为一次同时计算size和重儿子。5.3 扩展应用场景边权处理将边权下放到子节点处理可以支持路径边权查询。动态树LCT简化版对于某些特殊限制的动态树问题可以用重链剖分实现更简单的解决方案。结合树分块对于某些特殊问题可以结合树分块技术获得更好的时间复杂度。6. 重链剖分的局限性虽然重链剖分非常强大但也有其适用边界动态树问题对于频繁断边连边的场景LCTLink-Cut Tree更为适合。子树插入删除标准的重链剖分不支持高效的子树动态变化。特定查询类型如子树直径等复杂信息维护较为困难。常数因子相比倍增等简单算法重链剖分的预处理开销较大。在实际问题中需要根据具体需求选择合适的算法。重链剖分的优势在于其通用性和相对容易的实现难度特别适合处理静态树上的路径和子树操作。
