树链剖分（Heavy-Light Decomposition, HLD）是处理树上路径查询与修改问题的经典算法。它将一棵树分解为若干条不相交的链，使得任意树路径被拆分为至多 O(log n) 条链段，从而将路径问题转化为区间问题，配合线段树或树状数组实现 O(log² n) 的高效查询。本文用 Java 实现完整的树链剖分系统，涵盖重链分解、LCA 求解、路径查询与修改。
一、核心概念：重链与轻链
对于树中每个节点，计算其子树大小。子树最大的儿子称为重儿子，其余为轻儿子。连接节点与其重儿子的边构成重边，重边连续形成重链。由轻儿子出发的边称为轻边。
关键性质：从根到任意节点的路径上，轻边数量不超过 O(log n)。因此任意树路径可被拆分为至多 O(log n) 条重链。
二、算法流程
- 第一次 DFS：计算每个节点的父节点、深度、子树大小、重儿子
- 第二次 DFS：为每个节点分配链顶（top）和 DFS 序（dfn），确保同一条重链上的节点 DFS 序连续
- 建立线段树：在 DFS 序上建立线段树，支持区间查询/修改
- 路径操作：将路径拆分为多条重链，每条链对应线段树上的一个连续区间
三、Java 完整实现
import java.util.*;
/**
* 树链剖分（Heavy-Light Decomposition）
* 配合线段树实现树上路径查询与修改
*/
public class HeavyLightDecomposition {
private int n;
private List<Integer>[] adj;
// 树链剖分相关数组
private int[] parent; // 父节点
private int[] depth; // 深度
private int[] heavy; // 重儿子（-1表示无）
private int[] size; // 子树大小
private int[] top; // 链顶节点
private int[] dfn; // DFS序
private int[] rev; // dfn -> 节点映射
private int curDfn; // 当前DFS序计数
// 节点权值
private long[] value; // 原始节点权值
private long[] base; // 按DFS序排列的权值数组（线段树底层）
// 线段树
private SegmentTree segTree;
@SuppressWarnings("unchecked")
public HeavyLightDecomposition(int n) {
this.n = n;
this.adj = new ArrayList[n + 1];
for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
this.parent = new int[n + 1];
this.depth = new int[n + 1];
this.heavy = new int[n + 1];
this.size = new int[n + 1];
this.top = new int[n + 1];
this.dfn = new int[n + 1];
this.rev = new int[n + 1];
this.value = new long[n + 1];
this.base = new long[n + 1];
Arrays.fill(heavy, -1);
}
public void addEdge(int u, int v) {
adj[u].add(v);
adj[v].add(u);
}
public void setValue(int u, long val) {
value[u] = val;
}
/**
* 第一次DFS：计算子树大小和重儿子
*/
private void dfs1(int u, int p) {
parent[u] = p;
depth[u] = (p == 0) ? 0 : depth[p] + 1;
size[u] = 1;
int maxSize = 0;
for (int v : adj[u]) {
if (v != p) {
dfs1(v, u);
size[u] += size[v];
if (size[v] > maxSize) {
maxSize = size[v];
heavy[u] = v;
}
}
}
}
/**
* 第二次DFS：分配链顶和DFS序
*/
private void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++curDfn;
rev[curDfn] = u;
base[curDfn] = value[u];
if (heavy[u] != -1) {
dfs2(heavy[u], t); // 重儿子继承链顶
}
for (int v : adj[u]) {
if (v != parent[u] && v != heavy[u]) {
dfs2(v, v); // 轻儿子新建链
}
}
}
/**
* 初始化：执行两次DFS并建立线段树
*/
public void build(int root) {
dfs1(root, 0);
curDfn = 0;
dfs2(root, root);
segTree = new SegmentTree(base, n);
}
/**
* 求LCA（利用链顶）
*/
public int lca(int u, int v) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) {
int tmp = u; u = v; v = tmp;
}
u = parent[top[u]];
}
return depth[u] < depth[v] ? u : v;
}
/**
* 单点修改
*/
public void updatePoint(int u, long val) {
segTree.update(dfn[u], val);
}
/**
* 路径查询（区间和）
* 将u->v路径拆分为多条链，每条链在线段树上是连续区间
*/
public long queryPath(int u, int v) {
long res = 0;
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) {
int tmp = u; u = v; v = tmp;
}
// u所在链的顶端深度更大，先处理u的链
res += segTree.query(dfn[top[u]], dfn[u]);
u = parent[top[u]];
}
// 现在u和v在同一条链上
if (depth[u] > depth[v]) {
int tmp = u; u = v; v = tmp;
}
res += segTree.query(dfn[u], dfn[v]);
return res;
}
/**
* 路径修改（区间加）
*/
public void updatePath(int u, int v, long delta) {
while (top[u] != top[v]) {
if (depth[top[u]] < depth[top[v]]) {
int tmp = u; u = v; v = tmp;
}
segTree.rangeAdd(dfn[top[u]], dfn[u], delta);
u = parent[top[u]];
}
if (depth[u] > depth[v]) {
int tmp = u; u = v; v = tmp;
}
segTree.rangeAdd(dfn[u], dfn[v], delta);
}
/**
* 子树查询
* 子树在DFS序上是连续区间 [dfn[u], dfn[u] + size[u] - 1]
*/
public long querySubtree(int u) {
return segTree.query(dfn[u], dfn[u] + size[u] - 1);
}
/**
* 子树修改
*/
public void updateSubtree(int u, long delta) {
segTree.rangeAdd(dfn[u], dfn[u] + size[u] - 1, delta);
}
/**
* 线段树实现（支持区间和、区间加）
*/
public static class SegmentTree {
private int n;
private long[] tree; // 和值
private long[] lazy; // 懒标记（区间加）
public SegmentTree(long[] arr, int n) {
this.n = n;
this.tree = new long[n * 4];
this.lazy = new long[n * 4];
build(1, 1, n, arr);
}
private void build(int node, int l, int r, long[] arr) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(node << 1, l, mid, arr);
build(node << 1 | 1, mid + 1, r, arr);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
private void pushDown(int node, int l, int r) {
if (lazy[node] != 0) {
int mid = (l + r) >> 1;
int left = node << 1, right = node << 1 | 1;
lazy[left] += lazy[node];
lazy[right] += lazy[node];
tree[left] += lazy[node] * (mid - l + 1);
tree[right] += lazy[node] * (r - mid);
lazy[node] = 0;
}
}
public void update(int idx, long val) {
update(1, 1, n, idx, val);
}
private void update(int node, int l, int r, int idx, long val) {
if (l == r) {
tree[node] = val;
return;
}
pushDown(node, l, r);
int mid = (l + r) >> 1;
if (idx <= mid) update(node << 1, l, mid, idx, val);
else update(node << 1 | 1, mid + 1, r, idx, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
public void rangeAdd(int ql, int qr, long val) {
rangeAdd(1, 1, n, ql, qr, val);
}
private void rangeAdd(int node, int l, int r, int ql, int qr, long val) {
if (ql <= l && r <= qr) {
tree[node] += val * (r - l + 1);
lazy[node] += val;
return;
}
pushDown(node, l, r);
int mid = (l + r) >> 1;
if (ql <= mid) rangeAdd(node << 1, l, mid, ql, qr, val);
if (qr > mid) rangeAdd(node << 1 | 1, mid + 1, r, ql, qr, val);
tree[node] = tree[node << 1] + tree[node << 1 | 1];
}
public long query(int ql, int qr) {
return query(1, 1, n, ql, qr);
}
private long query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node];
pushDown(node, l, r);
int mid = (l + r) >> 1;
long res = 0;
if (ql <= mid) res += query(node << 1, l, mid, ql, qr);
if (qr > mid) res += query(node << 1 | 1, mid + 1, r, ql, qr);
return res;
}
}
public static void main(String[] args) {
// 构建测试树
// 1(10)
// / \
// 2(20) 3(30)
// / \ \
// 4(40) 5(50) 6(60)
// /
//7(70)
HeavyLightDecomposition hld = new HeavyLightDecomposition(7);
hld.addEdge(1, 2);
hld.addEdge(1, 3);
hld.addEdge(2, 4);
hld.addEdge(2, 5);
hld.addEdge(3, 6);
hld.addEdge(4, 7);
hld.setValue(1, 10);
hld.setValue(2, 20);
hld.setValue(3, 30);
hld.setValue(4, 40);
hld.setValue(5, 50);
hld.setValue(6, 60);
hld.setValue(7, 70);
hld.build(1);
System.out.println("=== 路径查询测试 ===");
System.out.println("路径 7->6 的权值和: " + hld.queryPath(7, 6)); // 70+40+20+10+30+60 = 230
System.out.println("路径 5->3 的权值和: " + hld.queryPath(5, 3)); // 50+20+10+30 = 110
System.out.println("路径 4->7 的权值和: " + hld.queryPath(4, 7)); // 40+70 = 110
System.out.println("\n=== LCA测试 ===");
System.out.println("LCA(7, 5) = " + hld.lca(7, 5)); // 2
System.out.println("LCA(7, 6) = " + hld.lca(7, 6)); // 1
System.out.println("LCA(4, 7) = " + hld.lca(4, 7)); // 4
System.out.println("\n=== 路径修改测试 ===");
hld.updatePath(7, 3, 5); // 路径7->3所有节点+5
System.out.println("路径修改后 7->6 的和: " + hld.queryPath(7, 6));
// 7:75, 4:45, 2:25, 1:15, 3:35, 6:60 => 75+45+25+15+35+60 = 255
System.out.println("\n=== 子树查询测试 ===");
System.out.println("子树2的权值和: " + hld.querySubtree(2)); // 25+45+75+50 = 195
System.out.println("\n=== 子树修改测试 ===");
hld.updateSubtree(2, 10);
System.out.println("子树2修改后的和: " + hld.querySubtree(2)); // +40 = 235
}
}
四、复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 建树（两次DFS） | O(n) | O(n) |
| 求LCA | O(log n) | O(1) |
| 路径查询 | O(log² n) | O(1) |
| 路径修改 | O(log² n) | O(1) |
| 子树查询 | O(log n) | O(1) |
| 子树修改 | O(log n) | O(1) |
路径操作复杂度为 O(log² n) 是因为路径被拆分为 O(log n) 条链，每条链在线段树上做一次 O(log n) 的查询。
五、算法对比与适用场景
| 方法 | 路径查询 | 路径修改 | 子树查询 | 子树修改 | 代码复杂度 |
|---|---|---|---|---|---|
| 树链剖分 | O(log² n) | O(log² n) | O(log n) | O(log n) | 中等 |
| 倍增法 | O(log n) | 不支持 | O(n) | 不支持 | 简单 |
| LCT | O(log n) | O(log n) | O(log n) | O(log n) | 复杂 |
| 欧拉序+线段树 | O(log n) | O(log n) | O(log n) | O(log n) | 简单 |
树链剖分的优势在于同时支持路径和子树操作，且常数较小，是竞赛和工程中的主流选择。
六、扩展与总结
树链剖分的思想还可应用于：
– 树上莫队：结合 HLD 将树上路径查询转化为序列莫队问题
– 动态树问题：与 Link-Cut Tree 配合处理树的动态修改
– 树形DP优化：在重链上使用线段树维护DP状态，实现 O(log² n) 的换根DP
掌握树链剖分，意味着掌握了将树结构问题线性化的核心能力，这是解决复杂树上查询问题的关键一步。
