树链剖分(Heavy-Light Decomposition)

树链剖分（Heavy-Light Decomposition，HLD）是一种用于 在树上快速处理路径或子树查询与修改 的数据结构技巧。
它的核心思想是：把树分解成若干条链，使树上的路径问题转化为若干段连续区间问题，然后用 线段树 / 树状数组 来维护。

核心思想：重儿子与轻边

树链剖分通过对节点的性质进行分类，将树拆解：

  1. 重子结点 (Heavy Child)：在所有子节点中，子树节点数最多的那个儿子。
  2. 轻子结点 (Light Child)：除重儿子以外的其他儿子。
  3. 重边 (Heavy Edge)：连接父节点与重儿子的边。
  4. 重链 (Heavy Path)：由多条重边首尾相接组成的链。
       1
     / | \
    2  3  4
   /\     |
  5  6    7 
 /
8
节点子节点重子结点轻子结点
12(sz=4), 3(sz=1), 4(sz=2)23，4
25(sz=2), 6(sz=1)56
47(sz=1)7无
58(sz=1)8无
3，6，7，8无无无

重边：1-2, 2-5, 5-8, 4-7
轻边：1-3, 1-4,2-6
重链：1-2-5-8, 4-7,3,6

为什么这么做？

通过这种划分，我们可以保证：从根节点到任何一个节点的路径上，经过的轻边数量和重链数量都不会超过 \(O(\log n)\)。 这就是树链剖分高效的原因。

常见应用：

  • 查询两点路径上的 和 / 最大值 / 最小值
  • 修改两点路径上的 权值
  • 查询某个子树
  • 结合 LCA

时间复杂度一般：

  • 预处理：(O(n))
  • 每次操作：\((O(\log^2 n))\)

一、核心思想

树链剖分的关键是把树拆成 重链（Heavy Chain）和轻边（Light Edge）。

定义：对于每个节点 (u)，找一个儿子 (v)，满足：size(v) =max(size(son))，这个儿子叫：重儿子（heavy son）

边：(u ->heavy_son) 是 重边,，其他边是 轻边，把所有重边连起来就形成 重链。

性质：从任意节点到根路径上，轻边最多 \((O(\log n))\) 条

这就是为什么查询复杂度是：\(\)O(\log^2 n)[\latex]

二、树链剖分做了什么

树链剖分主要做两件事：

1 建树 + 找重儿子

DFS 计算：

  • size[u] 子树大小
  • fa[u] 父节点
  • dep[u] 深度
  • son[u] 重儿子

代码：

void dfs1(int u,int f){
    fa[u]=f;
    dep[u]=dep[f]+1;
    size[u]=1;

    for(int v: g[u]){
        if(v==f) continue;
        dfs1(v,u);
        size[u]+=size[v];

        if(size[v]>size[son[u]])
            son[u]=v;
    }
}

2 剖分链

再 DFS 一次：

维护：

  • top[u]：当前链的顶端
  • dfn[u]：节点在线段树中的编号
  • rk[i]：编号对应的节点

代码：

void dfs2(int u,int t){
    top[u]=t;
    dfn[u]=++timer;
    rk[timer]=u;

    if(!son[u]) return;

    dfs2(son[u],t); // 重儿子继续在同一条链

    for(int v: g[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v); // 新链
    }
}

这样树就被映射成：一个 DFS 序数组

三、路径查询

假设查询：u 到 v 路径的和

思路：不断跳链。

如果：

top[u] != top[v]

说明不在同一条链。

让深度大的跳到链顶：

查询 [dfn[top[u]], dfn[u]]
u = fa[top[u]]

直到：

top[u] == top[v]

最后查询：

[dfn[u], dfn[v]]

代码：

int query_path(int u,int v){
    int ans=0;

    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);

        ans+=query(dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }

    if(dep[u]>dep[v])
        swap(u,v);

    ans+=query(dfn[u],dfn[v]);

    return ans;
}

四、子树查询

子树在 DFS 序中是 连续区间。

所以：

子树(u) = [dfn[u], dfn[u]+size[u]-1]

直接线段树查询即可。

query(dfn[u], dfn[u]+size[u]-1)

复杂度：O(og n)

五、整体复杂度

操作复杂度
建树O(n)
路径查询O(log² n)
路径修改O(log² n)
子树查询O(log n)

树链剖分 = 把树上的路径问题变成数组区间问题。

五、树链剖分需要的数组

数组含义
fa[u]父节点
dep[u]深度
size[u]子树大小
son[u]重儿子
top[u]所在链的顶端
dfn[u]DFS编号
seg[mode]线段树

十、完整 C++ 代码

这是 竞赛通用模板（LCA，路径和）

  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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2026-03-05 14:53:42
 * 最后修改: 2026-03-06 10:43:50
 * 文件描述: 用树链剖分求树上两结点权值之和
****************************************************************/

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;

// --- Segment Tree (range sum, point update) ---
long long seg[4 * MAXN];
/*
seg_update 是线段树的单点更新，把位置 idx 的值改为 val。
参数含义：
参数	     含义
node	    当前线段树节点编号（从1开始）
start/end	当前节点管辖的区间 [start, end]
idx	        要更新的位置（即 dfn[v]）
val	        新值
*/
void seg_update(int node, int start, int end, int idx, long long val) {
    if (start == end) { seg[node] = val; return; }
    int mid = (start + end) / 2;
    if (idx <= mid) seg_update(2*node, start, mid, idx, val);
    else            seg_update(2*node+1, mid+1, end, idx, val);
    seg[node] = seg[2*node] + seg[2*node+1];
}

long long seg_query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return seg[node];
    int mid = (start + end) / 2;
    return seg_query(2*node, start, mid, l, r)
         + seg_query(2*node+1, mid+1, end, l, r);
}

// --- HLD ---
int n;
vector<int> adj[MAXN];  //邻接表
long long val[MAXN];   // node values

int fa[MAXN], depth[MAXN], sz[MAXN], son[MAXN]; // 父节点、深度、子树大小(包括自己)、重儿子

/*top[v] — 节点 v 所在链的链顶（最浅的节点）

          1         链1: 1-2-5-7      → top[1]=top[2]=top[5]=top[7]=1
        /   \       链2: 9            → top[9]=9
       2     3      链3: 4            → top[4]=4
      / \   / \     链4: 3-8-10       → top[3]=top[8]=top[10]=3
     4   5 6   8    链5: 6            → top[6]=6
        / \     \
       7   9     10
dfn[v] — 节点 v 在线段树中的下标（按链优先顺序分配）
decompose 访问顺序: 1→2→5→7→9→4→3→8→10→6
dfn:               0  1  2  3  4  5  6  7   8  9
关键性质：同一条链上的节点，dfn 是连续的，所以链上的区间查询可以直接用线段树的 [dfn[top[v]], dfn[v]]。
*/

// 第一步：DFS 预处理每个节点的父节点、深度、子树大小和重儿子
void dfs(int v, int f) {
    fa[v] = f;
    depth[v] =depth[f] + 1;
    sz[v] = 1;
    for (int u : adj[v]) {
        if (u == f) continue;
        dfs(u, v);
        sz[v] += sz[u];
        if (sz[u] > sz[son[v]]) {
            son[v] = u;
        }
    }
}

int top[MAXN], dfn[MAXN], cur_dfn;              // 所在重链链顶、剖分后的编号、当前编号计数器
/*   1. 给每个节点分配 dfn（线段树下标），按"重链优先"顺序，保证同一条链的节点 dfn 连续。
     2. top[]记录每个节点的 top（所在链的链顶）。*/ 
void decompose(int v, int h) {
    top[v] = h;
    dfn[v]  = cur_dfn++;
    seg_update(1, 0, n - 1, dfn[v], val[v]);
    if(!son[v]) return;   //依赖全局初值和“无多测”假设。
    decompose(son[v], h);   // continue son chain

    for (int u : adj[v]) {
        if (u == fa[v] || u == son[v]) continue;
        decompose(u, u);          // start new chain
    }
}

// Step 3: u 到 v 路径上所有节点的权值和
long long path_query(int u, int v) {
    long long result = 0;
    while (top[u] != top[v]) {
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        // u is deeper: query from top[u] to u
        result += seg_query(1, 0, n - 1, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    // u and v are on the same chain now
    if (depth[u] > depth[v]) swap(u, v);
    result += seg_query(1, 0, n - 1, dfn[u], dfn[v]);
    return result;
}

// 仅查询两个节点的最近公共祖先（LCA）
int lca_query(int u, int v) {
    while (top[u] != top[v]) {
        //两条当前重链的链顶谁更深。
        if (depth[top[u]] < depth[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return depth[u] < depth[v] ? u : v;
}

// 修改某节点的权值
void point_update(int v, long long new_val) {
    val[v] = new_val;
    seg_update(1, 0, n - 1, dfn[v], new_val);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: n=10 tree
    //           1
    //         /   \
    //        2     3
    //       / \   / \
    //      4   5 6   8
    //         / \      \
    //        7   9      10
    n = 10;
    vector<pair<int,int>> edges = {
        {1,2},{1,3},{2,4},{2,5},{3,6},{3,8},{5,7},{5,9},{8,10}
    };
    for (auto& e : edges) {
        adj[e.first].push_back(e.second);
        adj[e.second].push_back(e.first);
    }

    for (int i = 1; i <= n; i++) val[i] = i;  // node i has value i

    dfs(1, 0);
    cur_dfn = 0;
    decompose(1, 1);

    // Query LCA: 7 and 10
    cout << "LCA of 7 and 10: " << lca_query(7, 10) << "\n"; // 1
    // Query path sum: 4 -> 7  (4->2->5->7)
    cout << "Sum on path 4->7: " << path_query(4, 7) << "\n"; // 4+2+5+7 = 18

    // Query path sum: 6 -> 4  (6-3-1-2-4)
    cout << "Sum on path 6->4: " << path_query(6, 4) << "\n"; // 6+3+1+2+4 = 16

    // Update node 2 to value 10
    point_update(2, 10);
    cout << "After update(2,10), sum on path 6->4: " << path_query(6, 4) << "\n"; // 6+3+1+10+4 = 24

    return 0;
}
Previous Lesson
Back to Lesson
Next Topic