跳转至

树链剖分

概述

树链剖分（Heavy-Light Decomposition，HLD）是一种将树分解为若干条不相交链的技术。通过将树上的路径问题转化为若干连续区间问题，结合线段树等数据结构，可以高效处理树上路径查询和修改问题。

核心思想：将树分解为重链和轻边，使得任意路径最多由 O(log n) 条重链组成。每条重链上的节点 DFS 序连续，可用线段树维护。

重链剖分原理

基本概念

概念 定义 说明
子树大小 size[u] 以 u 为根的子树节点数
重儿子 heavy[u] 使 size[v] 最大的子节点 v
轻儿子 其他儿子 除重儿子外的所有子节点
重边 (u, heavy[u]) 连接节点与其重儿子的边
轻边 其他边 连接节点与其轻儿子的边
重链 连续重边 由重边首尾相连形成的路径
链顶 top[u] 节点 u 所在重链的顶部节点

重链性质

关键性质：从任意节点到根的路径上，最多经过 O(log n) 条轻边。

证明：设当前节点为 u，经过轻边到达父节点 p。因为 u 是 p 的轻儿子，所以 size[u] ≤ size[p]/2。每经过一条轻边，子树大小至少减半，因此最多经过 log n 条轻边。

重链剖分可视化

示例树结构

1 2 5 6 3 4 7 8 9 10 11
根节点 重链1 重链3 其他节点

节点大小 (size)：

size[1] = 11整棵树
size[2] = 4节点 2,3,4,10
size[3] = 2节点 3,10
size[5] = 2节点 5,7
size[6] = 4节点 6,8,9,11
size[9] = 2节点 9,11
size[其他] = 1叶子节点
graph TB
    subgraph 重链剖分
        n1(("1<br/>size=11")) --> n2(("2<br/>size=4"))
        n1 --> n5(("5<br/>size=2"))
        n1 --> n6(("6<br/>size=4"))
        n2 --> n3(("3<br/>size=2"))
        n2 --> n4(("4<br/>size=1"))
        n3 --> n10(("10<br/>size=1"))
        n5 --> n7(("7<br/>size=1"))
        n6 --> n8(("8<br/>size=1"))
        n6 --> n9(("9<br/>size=2"))
        n9 --> n11(("11<br/>size=1"))
    end
    
    style n1 fill:#4CAF50,color:#fff
    style n2 fill:#2196F3,color:#fff
    style n3 fill:#2196F3,color:#fff
    style n10 fill:#2196F3,color:#fff
    style n6 fill:#FF9800,color:#fff
    style n9 fill:#FF9800,color:#fff
    style n11 fill:#FF9800,color:#fff

重儿子标记 (heavy)

heavy[1] = 2
size[2]=4 > size[5]=2, size[6]=4
heavy[2] = 3
size[3]=2 > size[4]=1
heavy[3] = 10
唯一子节点
heavy[6] = 9
size[9]=2 > size[8]=1
heavy[9] = 11
唯一子节点

重边（粗线）

1-2, 2-3, 3-10, 6-9, 9-11

轻边（细线）

1-5, 1-6, 2-4, 5-7, 6-8

重链划分

链1: 1 → 2 → 3 → 10 链2: 5 → 7 链3: 6 → 9 → 11 链4: 4 链5: 8

DFS 序与链顶

两遍 DFS 过程

第一遍 DFS：求子树大小和重儿子

flowchart TD
    A["DFS1: 自底向上计算"]
    B["遍历所有子节点"]
    C["累加子树大小: size[u] += size[v]"]
    D["找出最大子树: heavy[u] = argmax(size[v])"]
    E["返回父节点"]
    
    A --> B --> C --> D --> E
    
    style A fill:#E3F2FD
    style D fill:#4CAF50,color:#fff

第二遍 DFS：求链顶和 DFS 序

flowchart TD
    A["DFS2: 自顶向下分配"]
    B["优先遍历重儿子"]
    C["重儿子继承链顶: top[heavy] = top[u]"]
    D["DFS序连续: pos[u] = ++dfsCnt"]
    E["轻儿子开始新链: top[light] = light"]
    F["保证重链节点DFS序连续"]
    
    A --> B --> C --> D --> E --> F
    
    style A fill:#E3F2FD
    style F fill:#E8F5E9

DFS 序分配

第二遍 DFS 执行过程

DFS2(1, 1): top[1]=1, pos[1]=1
→ DFS2(2, 1): top[2]=1, pos[2]=2 (重儿子，继承链顶)
→ DFS2(3, 1): top[3]=1, pos[3]=3
→ DFS2(10, 1): top[10]=1, pos[10]=4
→ DFS2(4, 4): top[4]=4, pos[4]=5 (轻儿子，开始新链)
→ DFS2(5, 5): top[5]=5, pos[5]=6 (轻儿子，开始新链)
→ DFS2(7, 5): top[7]=5, pos[7]=7
→ DFS2(6, 6): top[6]=6, pos[6]=8 (轻儿子，开始新链)
→ DFS2(9, 6): top[9]=6, pos[9]=9 (重儿子，继承链顶)
→ DFS2(11, 6): top[11]=6, pos[11]=10
→ DFS2(8, 8): top[8]=8, pos[8]=11

最终结果

节点1234567891011
pos1235687119410
top11145658616

DFS 序与重链对应关系：

DFS序1234567891011
节点1231045769118
链顶11114556668
重链重链1轻链重链2重链3轻链
关键观察：同一重链上的节点 DFS 序连续！这使得我们可以用线段树高效维护重链上的信息。

数据结构定义

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#define MAXN 100005

int n;
int head[MAXN], to[2 * MAXN], next[2 * MAXN], edgeCnt;  // 邻接表
int weight[MAXN];        // 节点权值
int parent[MAXN];        // 父节点
int depth[MAXN];         // 深度
int size[MAXN];          // 子树大小
int heavy[MAXN];         // 重儿子
int top[MAXN];           // 链顶
int pos[MAXN];           // DFS序
int dfsOrder[MAXN];      // DFS序对应的节点
int dfsCnt;              // DFS序计数器

void addEdge(int u, int v) {
    to[++edgeCnt] = v;
    next[edgeCnt] = head[u];
    head[u] = edgeCnt;
}

第一遍 DFS：求重儿子

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs1(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    size[u] = 1;
    heavy[u] = -1;
    
    int maxSize = 0;
    
    for (int e = head[u]; e; e = next[e]) {
        int v = to[e];
        if (v == p) continue;
        
        dfs1(v, u, d + 1);
        size[u] += size[v];
        
        // 找子树最大的儿子作为重儿子
        if (size[v] > maxSize) {
            maxSize = size[v];
            heavy[u] = v;
        }
    }
}

第二遍 DFS：求链顶和 DFS 序

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void dfs2(int u, int t) {
    top[u] = t;              // 设置链顶
    pos[u] = ++dfsCnt;       // 分配DFS序
    dfsOrder[dfsCnt] = u;    // 记录DFS序对应节点
    
    // 优先遍历重儿子（保证重链DFS序连续）
    if (heavy[u] != -1) {
        dfs2(heavy[u], t);   // 重儿子继承链顶
    }
    
    // 遍历轻儿子
    for (int e = head[u]; e; e = next[e]) {
        int v = to[e];
        if (v == parent[u] || v == heavy[u]) continue;
        dfs2(v, v);          // 轻儿子开始新链
    }
}

路径查询

原理

路径查询的核心是将路径分解为若干重链片段：

flowchart TD
    A["路径 u → v"]
    B["u, v 不在同一重链?"]
    C["选择链顶较深的节点"]
    D["查询从链顶到该节点的区间"]
    E["跳到链顶的父节点"]
    F["u, v 在同一重链"]
    G["查询 pos[u] 到 pos[v] 的区间"]
    H["合并所有区间结果"]
    
    A --> B
    B -->|是| C --> D --> E --> B
    B -->|否| F --> G --> H
    E --> H
    
    style A fill:#E3F2FD
    style H fill:#E8F5E9

实现代码

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int tree[4 * MAXN];

void build(int node, int l, int r) {
    if (l == r) {
        tree[node] = weight[dfsOrder[l]];
        return;
    }
    
    int mid = (l + r) / 2;
    build(2 * node, l, mid);
    build(2 * node + 1, mid + 1, r);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int queryTree(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[node];
    if (r < ql || l > qr) return 0;
    
    int mid = (l + r) / 2;
    return queryTree(2 * node, l, mid, ql, qr) + 
           queryTree(2 * node + 1, mid + 1, r, ql, qr);
}

int queryPath(int u, int v) {
    int result = 0;
    
    // 当 u 和 v 不在同一重链时
    while (top[u] != top[v]) {
        // 让链顶较深的节点往上跳
        if (depth[top[u]] < depth[top[v]]) {
            int temp = u; u = v; v = temp;
        }
        
        // 查询从链顶到 u 的区间
        result += queryTree(1, 1, n, pos[top[u]], pos[u]);
        // 跳到链顶的父节点
        u = parent[top[u]];
    }
    
    // u 和 v 在同一重链上
    if (depth[u] > depth[v]) {
        int temp = u; u = v; v = temp;
    }
    
    result += queryTree(1, 1, n, pos[u], pos[v]);
    
    return result;
}

查询示例

查询路径 10 → 11 的和

步骤1

top[10]=1, top[11]=6, 不在同一链

depth[top[10]]=1 < depth[top[11]]=3

交换: u=11, v=10

步骤2

查询 [pos[6], pos[11]] = [8, 10]

result += queryTree(8, 10)

u = parent[6] = 1

步骤3

top[1]=1, top[10]=1, 在同一链

depth[1]=0 < depth[10]=3

查询 [pos[1], pos[10]] = [1, 4]

result += queryTree(1, 4)

路径分解为两个区间

[8, 10]: 节点 6, 9, 11 (重链3的一部分) [1, 4]: 节点 1, 2, 3, 10 (重链1) 
graph TB
    subgraph 路径查询分解
        n10(("10")) -.-> n3(("3"))
        n3 -.-> n2(("2"))
        n2 -.-> n1(("1"))
        n1 -.-> n6(("6"))
        n6 -.-> n9(("9"))
        n9 -.-> n11(("11"))
    end
    
    style n10 fill:#FF5722,color:#fff
    style n11 fill:#FF5722,color:#fff
    style n1 fill:#4CAF50,color:#fff
    style n2 fill:#4CAF50,color:#fff
    style n3 fill:#4CAF50,color:#fff
    style n6 fill:#2196F3,color:#fff
    style n9 fill:#2196F3,color:#fff

路径更新

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
void updateTree(int node, int l, int r, int idx, int val) {
    if (l == r) {
        tree[node] = val;
        return;
    }
    
    int mid = (l + r) / 2;
    if (idx <= mid) {
        updateTree(2 * node, l, mid, idx, val);
    } else {
        updateTree(2 * node + 1, mid + 1, r, idx, val);
    }
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

void updatePoint(int u, int val) {
    weight[u] = val;
    updateTree(1, 1, n, pos[u], val);
}

区间路径更新

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
void updateRangeTree(int node, int l, int r, int ql, int qr, int val);

void updatePath(int u, int v, int val) {
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            int temp = u; u = v; v = temp;
        }
        updateRangeTree(1, 1, n, pos[top[u]], pos[u], val);
        u = parent[top[u]];
    }
    
    if (depth[u] > depth[v]) {
        int temp = u; u = v; v = temp;
    }
    updateRangeTree(1, 1, n, pos[u], pos[v], val);
}

最近公共祖先（LCA）

利用树链剖分求 LCA：

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int lca(int u, int v) {
    // 让 u 和 v 跳到同一重链
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) {
            int temp = u; u = v; v = temp;
        }
        u = parent[top[u]];  // 跳过整条重链
    }
    
    // 在同一重链上，深度浅的是 LCA
    return (depth[u] < depth[v]) ? u : v;
}

LCA 查询示例：

求 LCA(10, 11)

步骤1

top[10]=1, top[11]=6, 不在同一链

depth[top[10]]=1 < depth[top[11]]=3

交换: u=11, v=10

u = parent[top[11]] = parent[6] = 1

步骤2

top[1]=1, top[10]=1, 在同一链

depth[1]=0 < depth[10]=3

结果: LCA(10, 11) = 1

子树操作

子树内的节点 DFS 序连续，可直接查询：

C
1
2
3
4
5
6
7
8
9
// 查询子树和
int querySubtree(int u) {
    return queryTree(1, 1, n, pos[u], pos[u] + size[u] - 1);
}

// 更新子树
void updateSubtree(int u, int val) {
    updateRangeTree(1, 1, n, pos[u], pos[u] + size[u] - 1, val);
}
子树操作的优势：子树内所有节点的 DFS 序形成连续区间 [pos[u], pos[u] + size[u] - 1]，可以在 O(log n) 时间内完成子树查询/更新，无需路径分解。

C++ 实现

C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <vector>
#include <algorithm>

class HeavyLightDecomposition {
private:
    std::vector<std::vector<int>> adj;
    std::vector<int> parent, depth, size, heavy, top, pos;
    std::vector<int> values, tree;
    int n, dfsCnt;
    
    void dfs1(int u, int p) {
        parent[u] = p;
        size[u] = 1;
        heavy[u] = -1;
        int maxSize = 0;
        
        for (int v : adj[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            dfs1(v, u);
            size[u] += size[v];
            if (size[v] > maxSize) {
                maxSize = size[v];
                heavy[u] = v;
            }
        }
    }
    
    void dfs2(int u, int t) {
        top[u] = t;
        pos[u] = ++dfsCnt;
        
        if (heavy[u] != -1) dfs2(heavy[u], t);
        
        for (int v : adj[u]) {
            if (v == parent[u] || v == heavy[u]) continue;
            dfs2(v, v);
        }
    }
    
    void build(int node, int l, int r) {
        if (l == r) {
            tree[node] = values[pos[l]];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    int queryTree(int node, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return tree[node];
        if (r < ql || l > qr) return 0;
        int mid = (l + r) / 2;
        return queryTree(2 * node, l, mid, ql, qr) + 
               queryTree(2 * node + 1, mid + 1, r, ql, qr);
    }
    
public:
    HeavyLightDecomposition(int n) : n(n), adj(n + 1), parent(n + 1), 
        depth(n + 1), size(n + 1), heavy(n + 1), top(n + 1), 
        pos(n + 1), values(n + 1), tree(4 * n + 5), dfsCnt(0) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    void build() {
        dfs1(1, 0);
        dfs2(1, 1);
        build(1, 1, n);
    }
    
    int queryPath(int u, int v) {
        int result = 0;
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
            result += queryTree(1, 1, n, pos[top[u]], pos[u]);
            u = parent[top[u]];
        }
        if (depth[u] > depth[v]) std::swap(u, v);
        result += queryTree(1, 1, n, pos[u], pos[v]);
        return result;
    }
    
    int querySubtree(int u) {
        return queryTree(1, 1, n, pos[u], pos[u] + size[u] - 1);
    }
    
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (depth[top[u]] < depth[top[v]]) std::swap(u, v);
            u = parent[top[u]];
        }
        return (depth[u] < depth[v]) ? u : v;
    }
    
    int dist(int u, int v) {
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
};

时间复杂度分析

操作 时间复杂度 说明
预处理 O(n) 两遍 DFS
路径查询 O(log² n) 最多 O(log n) 条重链，每条 O(log n)
路径更新 O(log² n) 同路径查询
LCA 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(log n) = O(log² n)
优化提示：使用支持 O(log n) 区间查询的数据结构（如线段树）时，路径操作为 O(log²n)。若使用更高效的数据结构（如 Splay 树），可优化到 O(log n)。

空间复杂度

数据 空间复杂度 说明
邻接表 O(n) 存储树结构
剖分信息 O(n) parent, depth, size, heavy, top, pos
线段树 O(n) 4n 大小
总计 O(n) 线性空间

剖分类型对比

剖分类型 链数上界 适用场景
重链剖分 O(log n) 通用，路径操作
长链剖分 O(√n) 子树深度相关问题
轻重链剖分 O(log n) 实际常数更优

应用场景

1. 树上路径查询

C++
1
2
3
4
5
6
7
8
// 路径和
int pathSum(int u, int v) { return queryPath(u, v); }

// 路径最大值（线段树改为维护最大值）
int pathMax(int u, int v);

// 路径第K大（需要可持久化线段树）
int pathKth(int u, int v, int k);

2. 树上路径更新

C++
1
2
3
4
5
6
7
8
// 路径加
void pathAdd(int u, int v, int val);

// 路径赋值
void pathAssign(int u, int v, int val);

// 路径翻转（01树）
void pathFlip(int u, int v);

3. 子树操作

C++
1
2
3
4
5
// 子树和
int subtreeSum(int u) { return querySubtree(u); }

// 子树加
void subtreeAdd(int u, int val);

4. 树上差分

C++
1
2
3
4
5
6
7
8
// 路径修改转单点修改
void pathDiff(int u, int v, int val) {
    int l = lca(u, v);
    diff[u] += val;
    diff[v] += val;
    diff[l] -= val;
    diff[parent[l]] -= val;
}

典型问题示例

LeetCode 2642. 设计图最短路径（树特例）

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class TreePathQuery {
private:
    HeavyLightDecomposition hld;
    
public:
    TreePathQuery(int n, vector<vector<int>>& edges, vector<int>& values) 
        : hld(n) {
        for (auto& e : edges) {
            hld.addEdge(e[0] + 1, e[1] + 1);
        }
        hld.build();
    }
    
    int queryPath(int u, int v) {
        return hld.queryPath(u + 1, v + 1);
    }
};

树链剖分 vs 其他方法

方法 路径查询 子树查询 LCA 实现复杂度
树链剖分 O(log²n) O(log n) O(log n) 中等
树上差分 O(n) O(n) O(log n) 简单
欧拉序+RMQ 不支持 O(log n) O(1) 简单
点分治 O(n log n) 不支持 不支持 复杂
选择建议：当需要同时支持路径查询、子树查询、LCA 等多种操作时，树链剖分是最通用和高效的方案。

参考资料

  • 《算法竞赛入门经典》树链剖分章节
  • Heavy-Light Decomposition 论文 (Sleator & Tarjan, 1983)
  • 《挑战程序设计竞赛》树链剖分应用