本课时有配套视频讲解，购买后即可观看（永久有效）
树上差分
一、课上练习
编程练习
- 压力最大的隔间：L49981
二、知识总结
✨ 核心思想
树上差分是将一维数组差分的思想推广到树结构上的技巧。在树上对一条路径进行区间修改时，利用 LCA 将修改转化为若干个点上的差分标记，最后通过一次 DFS 汇总得到每个节点的实际值。树上差分分为点差分和边差分两种。
✨ 算法原理
一维差分回顾
在数组 a 上对区间 [l, r] 每个元素加 val：
d[l] += vald[r+1] -= val- 求前缀和后得到修改后的数组
树上点差分
对路径 u 到 v 上的所有节点加 val（设 LCA(u,v) = w，w 的父节点为 p）：
d[u] += vald[v] += vald[w] -= vald[parent(w)] -= val
最后对树做一次 DFS，自底向上汇总子树的 d 值之和，就是每个节点的实际增量。
原理解释： 从 u 到根的路径和从 v 到根的路径，重叠部分是从 w 到根。u 和 v 各打 +val 标记，w 处打 -val 抵消多算的一次，parent(w) 处打 -val 抵消 w 以上被多算的部分。
树上边差分
对路径 u 到 v 上的所有边加 val（设 LCA(u,v) = w）：
d[u] += vald[v] += vald[w] -= 2 * val
每条边的值等于其子节点的 d 值子树和。
原理解释： 边差分中，边 (u, parent(u)) 的值用子节点 u 的子树 d 值之和表示。u 和 v 各打 +val，w 处打 -2val（因为 w 上方的边不需要修改，而 u 和 v 到 w 的路径各贡献了一次 w）。
✨ 代码实现
1#include <iostream>
2#include <vector>
3#include <cstring>
4using namespace std;
5
6const int MAXN = 500005;
7const int LOG = 20;
8
9vector<int> adj[MAXN];
10int fa[MAXN][LOG], dep[MAXN];
11int d[MAXN]; // 差分数组
12long long val[MAXN]; // 最终每个节点的值
13int n, m;
14
15// DFS预处理深度和倍增数组
16void dfsInit(int u, int f, int depth) {
17 fa[u][0] = f;
18 dep[u] = depth;
19 for (int k = 1; k < LOG; k++)
20 fa[u][k] = fa[fa[u][k-1]][k-1];
21 for (int v : adj[u]) {
22 if (v == f) continue;
23 dfsInit(v, u, depth + 1);
24 }
25}
26
27// 求LCA
28int lca(int u, int v) {
29 if (dep[u] < dep[v]) swap(u, v);
30 int diff = dep[u] - dep[v];
31 for (int k = 0; k < LOG; k++)
32 if ((diff >> k) & 1) u = fa[u][k];
33 if (u == v) return u;
34 for (int k = LOG - 1; k >= 0; k--)
35 if (fa[u][k] != fa[v][k]) {
36 u = fa[u][k];
37 v = fa[v][k];
38 }
39 return fa[u][0];
40}
41
42// DFS汇总：自底向上累加差分值
43void dfsSum(int u, int f) {
44 val[u] = d[u]; // 初始为差分值
45 for (int v : adj[u]) {
46 if (v == f) continue;
47 dfsSum(v, u);
48 val[u] += val[v]; // 累加子树的值
49 }
50}
51
52int main() {
53 ios::sync_with_stdio(false);
54 cin.tie(nullptr);
55
56 cin >> n >> m;
57 for (int i = 0; i < n - 1; i++) {
58 int u, v;
59 cin >> u >> v;
60 adj[u].push_back(v);
61 adj[v].push_back(u);
62 }
63
64 dfsInit(1, 0, 0);
65
66 // m次路径修改操作
67 memset(d, 0, sizeof(d));
68 for (int i = 0; i < m; i++) {
69 int u, v, w;
70 cin >> u >> v >> w; // 路径u→v上每个节点加w
71 int l = lca(u, v);
72 // 点差分
73 d[u] += w;
74 d[v] += w;
75 d[l] -= w;
76 if (fa[l][0] != 0) { // l不是根
77 d[fa[l][0]] -= w;
78 }
79 }
80
81 // 汇总
82 dfsSum(1, 0);
83
84 // 输出每个节点的值
85 for (int i = 1; i <= n; i++) {
86 cout << val[i] << " \n"[i == n];
87 }
88
89 return 0;
90}1#include <iostream>
2#include <vector>
3#include <cstring>
4using namespace std;
5
6const int MAXN = 500005;
7const int LOG = 20;
8
9vector<int> adj[MAXN];
10int fa[MAXN][LOG], dep[MAXN];
11int d[MAXN]; // 差分数组（标记在节点上，表示其与父节点间的边）
12long long edgeVal[MAXN]; // 每条边的最终值（用子节点编号标识边）
13int n, m;
14
15void dfsInit(int u, int f, int depth) {
16 fa[u][0] = f;
17 dep[u] = depth;
18 for (int k = 1; k < LOG; k++)
19 fa[u][k] = fa[fa[u][k-1]][k-1];
20 for (int v : adj[u]) {
21 if (v == f) continue;
22 dfsInit(v, u, depth + 1);
23 }
24}
25
26int lca(int u, int v) {
27 if (dep[u] < dep[v]) swap(u, v);
28 int diff = dep[u] - dep[v];
29 for (int k = 0; k < LOG; k++)
30 if ((diff >> k) & 1) u = fa[u][k];
31 if (u == v) return u;
32 for (int k = LOG - 1; k >= 0; k--)
33 if (fa[u][k] != fa[v][k]) {
34 u = fa[u][k];
35 v = fa[v][k];
36 }
37 return fa[u][0];
38}
39
40// DFS汇总边差分
41void dfsSum(int u, int f) {
42 edgeVal[u] = d[u];
43 for (int v : adj[u]) {
44 if (v == f) continue;
45 dfsSum(v, u);
46 edgeVal[u] += edgeVal[v];
47 }
48}
49
50int main() {
51 ios::sync_with_stdio(false);
52 cin.tie(nullptr);
53
54 cin >> n >> m;
55 for (int i = 0; i < n - 1; i++) {
56 int u, v;
57 cin >> u >> v;
58 adj[u].push_back(v);
59 adj[v].push_back(u);
60 }
61
62 dfsInit(1, 0, 0);
63
64 memset(d, 0, sizeof(d));
65 for (int i = 0; i < m; i++) {
66 int u, v, w;
67 cin >> u >> v >> w; // 路径u→v上每条边加w
68 int l = lca(u, v);
69 // 边差分
70 d[u] += w;
71 d[v] += w;
72 d[l] -= 2 * w;
73 }
74
75 dfsSum(1, 0);
76
77 // edgeVal[u] 表示边 (u, parent(u)) 的值
78 // 注意根节点没有"上方"的边
79 for (int i = 2; i <= n; i++) {
80 cout << "边 (" << i << ", " << fa[i][0]
81 << ") 的值：" << edgeVal[i] << endl;
82 }
83
84 return 0;
85}✨ 执行示例
以下面的树为例：
1
/ \
2 3
/ \
4 5操作：路径 4 到 3 上每个节点加 1（点差分）
1LCA(4, 3) = 1
2
3差分操作：
4 d[4] += 1 → d[4] = 1
5 d[3] += 1 → d[3] = 1
6 d[1] -= 1 → d[1] = -1
7 d[parent(1)] -= 1 → 1是根，跳过
8
9差分数组 d: [0, -1, 0, 1, 1, 0]
10
11DFS汇总（自底向上）：
12 节点4: val[4] = d[4] = 1
13 节点5: val[5] = d[5] = 0
14 节点2: val[2] = d[2] + val[4] + val[5] = 0 + 1 + 0 = 1
15 节点3: val[3] = d[3] = 1
16 节点1: val[1] = d[1] + val[2] + val[3] = -1 + 1 + 1 = 1
17
18最终值: 1→1, 2→1, 3→1, 4→1, 5→0
19路径 4→2→1→3 上的节点都加了1
20节点5不在路径上，值为0再增加一次操作：路径 4 到 5 上每个节点加 2
1LCA(4, 5) = 2
2
3差分操作：
4 d[4] += 2 → d[4] = 3
5 d[5] += 2 → d[5] = 2
6 d[2] -= 2 → d[2] = -2
7 d[1] -= 2 → d[1] = -3
8
9DFS汇总：
10 节点4: val[4] = 3
11 节点5: val[5] = 2
12 节点2: val[2] = -2 + 3 + 2 = 3
13 节点3: val[3] = 1
14 节点1: val[1] = -3 + 3 + 1 = 1
15
16最终值: 1→1, 2→3, 3→1, 4→3, 5→2
17验证：
18 节点2在两条路径上（+1+2=3）
19 节点4在两条路径上（+1+2=3）
20 节点5只在第二条路径上（+2）✨ 解题步骤详解
- 建树并预处理 LCA：DFS 求深度 + 倍增预处理
- 判断是点差分还是边差分：
- 修改路径上的节点 → 点差分
- 修改路径上的边 → 边差分
- 对每次修改操作打差分标记：
- 点差分：
d[u]+=w, d[v]+=w, d[lca]-=w, d[parent(lca)]-=w - 边差分：
d[u]+=w, d[v]+=w, d[lca]-=2w
- 点差分：
- DFS 汇总：自底向上累加子树的差分值
- 输出结果
✨ 常见错误
- 点差分和边差分公式搞混：点差分在 LCA 和其父节点各减一次，边差分在 LCA 处减两次
- 根节点的父节点处理：根节点没有父节点，点差分时需要特判
- 边差分时对应关系错误：边 (u, parent(u)) 的值存在节点 u 上（而非 parent(u)）
- 汇总方向错误：必须自底向上（后序遍历），不能自顶向下
- 多次操作后忘记清零差分数组：如果有多组数据需要注意
- LCA 预处理不正确导致差分位置错误
✨ 算法评价
| 指标 | 值 |
|---|---|
| 预处理时间 | O(n log n)（LCA 预处理） |
| 单次修改 | O(log n)（求 LCA） |
| 汇总时间 | O(n)（一次 DFS） |
| m 次修改总时间 | O(n log n + m log n) |
| 空间复杂度 | O(n log n) |
适用场景：
- 多次路径修改 + 一次全局查询
- 离线处理：所有修改操作结束后统一查询
- 不需要在修改过程中实时查询
不适用场景（应使用树链剖分+线段树）：
- 修改和查询交替进行
- 需要动态查询某条路径或子树的值