一、算法概述
树上差分（Tree Difference）是一种将”数组差分”思想延伸到树形结构上的算法。它能够在 O(1) 的时间内把”对路径上所有边/点进行统一修改”的操作记录下来，并通过一次 O(n) 的子树求和（DFS 累加）将所有修改一次性应用到结果中。配合 LCA（最近公共祖先）预处理，树上差分可以高效解决”路径权值统计”、”路径修改”、”路径计数”等大量题目。
它的核心价值是把”区间”这一维度的概念自然地拓展到了”路径”维度。在数轴上，区间 [l, r] 上的差分是把 diff[l]++ 与 diff[r+1]--；在树上，路径 (u, v) 上的差分则是把 cnt[u]++、cnt[v]++、cnt[lca(u, v)] -= 2（如果统计的是边权）或 cnt[lca(u, v)]-- 与 cnt[parent(lca(u, v))]--（如果统计的是点权）。
本文将系统介绍树上点差分、边差分、子树差分三种常见形式，并给出可直接运行的 Java 实现。
二、算法原理
2.1 数轴上的差分回顾
设原数组 a[]，差分数组 d[] 满足 d[i] = a[i] - a[i-1]。那么区间 [l, r] 整体加 v 的操作，等价于：
d[l] += v
d[r+1] -= v
最后再对 d[] 做一次前缀和就得到了”加了 v 之后”的 a[]。这种”延迟应用”的优势在于，对区间的修改可以是 O(1) 的，无论区间有多长。
2.2 树上点差分
对树上的两个结点 u 和 v，我们希望给路径 (u, v) 上的每个结点的点权都加 v。做法是：
cnt[u] += v；cnt[v] += v；cnt[lca(u, v)] -= v；cnt[parent[lca(u, v)]] -= v（如果存在父结点）。
为什么要这样做？设 w = lca(u, v)，路径 (u, v) 上的结点等于：
– u -> w 路径上的所有结点（不包括 w）；
– v -> w 路径上的所有结点（不包括 w）；
– 加上 w 本身。
如果我们把 u 和 v 都 +v，再把 lca 减去 2v，那么当我们从叶子向根做子树累加时：
– u 到 w（不含 w）之间，每个结点的累计贡献恰好是 +v；
– v 到 w（不含 w）之间同理；
– w 的累计贡献为 v + v - 2v = 0，也就是说 w 没有被加 v。这是不对的——w 应该是被加 v 的那个点。
– 所以我们额外在 parent[w] 处再减 v，这样当累计到 parent[w] 时，子树贡献被减回，w 本身的贡献就恢复为 +v。
这就是经典的”点差分四步法”。
2.3 树上边差分
如果修改的对象是边（而不是点），那么”路径 (u, v) 上的边”恰好等于 u -> v 路径上”不包括 lca 的“那些边所关联的结点之上的边。换句话说，每条被修改的边对应它深度更深的那个端点。因此做法是：
cnt[u] += v；cnt[v] += v；cnt[lca(u, v)] -= 2v。
最后做子树累加时，每个结点的 cnt 就表示”以它为下端点（深度更深的端点）的边需要被修改 v 次”。这也是常用形式。
2.4 子树差分
如果要修改的不是路径而是某个结点 x 的整棵子树（如把子树内所有点的点权 +v），那么就直接：
cnt[x] += v
cnt[parent[x] + 1] -= v // 出子树时减去
这种形式比较简单，结合 DFS 序后可以直接用线段树或 BIT 处理。
2.5 LCA 预处理
整套算法需要 O(n log n) 预处理 LCA。常见做法是”二分父亲 + 倍增”，即 up[k][i] 表示结点 i 的第 2^k 个祖先。查询 lca(u, v) 时，先把 u 和 v 提到同一深度，再从大到小尝试往上跳，找到最后一个不同的祖先即为 LCA。
整体复杂度：
– 预处理 O((n + q) log n)；
– 每次差分修改 O(1)；
– 最后做一次 DFS 累加 O(n)。
三、Java 实现
下面给出一个完整的、可直接运行的 Java 实现。包含：
– LCA 预处理（倍增法）；
– TreeDiff 类：支持点差分、边差分、子树差分；
– main 方法：演示一棵 8 个结点的二叉树，给多条路径做差分并求最终结果。
import java.util.*;
/**
* 树上差分（Tree Difference）+ 倍增 LCA
*
* 支持：
* 1. 点差分：路径 u -> v 上每个点权 + val
* 2. 边差分：路径 u -> v 上每条边 + val（最终累加到深度更深的端点上）
* 3. 子树差分：把整棵子树内的点权 + val
*
* 时间复杂度：
* - LCA 预处理：O(n log n)
* - 单次修改：O(1)
* - 累加：O(n)
*/
public class TreeDifference {
/** 图的邻接表（无根树，但这里从 1 开始） */
private final List<List<Integer>> g;
/** 结点数量 */
private final int n;
/** 根结点的父结点：通常设为 0 */
private final int root;
/** 深度数组 */
private final int[] depth;
/** 倍增祖先表 up[k][i]：结点 i 的第 2^k 个祖先 */
private final int[][] up;
/** 子树大小（DFS 序统计用） */
private final int[] subSize;
/** DFS 序：tin / tout */
private final int[] tin, tout;
/** 当前时间戳 */
private int timer = 0;
/** 差分标记：cnt[i] 表示最终要累加到结点 i 上的值（点差分 / 边差分都用同一数组） */
private final long[] cnt;
/** 最终结果数组 */
private final long[] result;
/** 树的深度（log2(n) 上取整） */
private final int LOG;
public TreeDifference(int n, int root) {
this.n = n;
this.root = root;
this.g = new ArrayList<>();
for (int i = 0; i <= n; i++) g.add(new ArrayList<>());
this.LOG = 32 - Integer.numberOfLeadingZeros(n);
this.depth = new int[n + 1];
this.up = new int[LOG][n + 1];
this.subSize = new int[n + 1];
this.tin = new int[n + 1];
this.tout = new int[n + 1];
this.cnt = new long[n + 1];
this.result = new long[n + 1];
}
/** 加边（无向） */
public void addEdge(int u, int v) {
g.get(u).add(v);
g.get(v).add(u);
}
/** DFS 预处理深度、父亲、DFS 序 */
private void dfs(int u, int p) {
tin[u] = ++timer;
up[0][u] = p;
depth[u] = depth[p] + 1;
subSize[u] = 1;
for (int k = 1; k < LOG; k++) {
up[k][u] = up[k - 1][up[k - 1][u]];
}
for (int v : g.get(u)) {
if (v == p) continue;
dfs(v, u);
subSize[u] += subSize[v];
}
tout[u] = timer;
}
/** LCA 查询（要求已经调用过 prepare） */
public int lca(int u, int v) {
if (depth[u] < depth[v]) {
int tmp = u; u = v; v = tmp;
}
// 把 u 提到和 v 同深度
int diff = depth[u] - depth[v];
for (int k = 0; k < LOG; k++) {
if (((diff >> k) & 1) == 1) {
u = up[k][u];
}
}
if (u == v) return u;
// 从大到小尝试往上跳
for (int k = LOG - 1; k >= 0; k--) {
if (up[k][u] != up[k][v]) {
u = up[k][u];
v = up[k][v];
}
}
return up[0][u];
}
/** 判断 a 是否是 b 的祖先 */
public boolean isAncestor(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
/** 预处理（必须在所有 addEdge 后调用一次） */
public void prepare() {
timer = 0;
dfs(root, 0);
}
/**
* 点差分：把路径 u -> v 上的每个点权 + val
*/
public void addPathPoint(int u, int v, long val) {
int w = lca(u, v);
cnt[u] += val;
cnt[v] += val;
cnt[w] -= val;
if (up[0][w] != 0) {
cnt[up[0][w]] -= val;
}
}
/**
* 边差分：把路径 u -> v 上的每条边权 + val
* 累加后，cnt[i] 表示"以 i 为下端点的边"被加了多少次
*/
public void addPathEdge(int u, int v, long val) {
int w = lca(u, v);
cnt[u] += val;
cnt[v] += val;
cnt[w] -= 2 * val;
}
/**
* 子树差分：把以 u 为根的整棵子树内的所有点权 + val
*/
public void addSubtreePoint(int u, long val) {
cnt[u] += val;
cnt[up[0][u]] -= val;
}
/** 第二次 DFS：把差分标记累加到 result 中 */
private void dfsPushUp(int u, int p) {
for (int v : g.get(u)) {
if (v == p) continue;
dfsPushUp(v, u);
cnt[u] += cnt[v];
}
result[u] = cnt[u];
}
/**
* 应用所有差分，得到每个结点的最终值。
* 注意：调用前必须已经 addPathPoint/addPathEdge 等操作完成了。
*/
public long[] apply() {
// 注意：cnt 数组会被修改，所以如果要重复应用，需要备份
dfsPushUp(root, 0);
return result;
}
/** 重置差分数组 */
public void reset() {
Arrays.fill(cnt, 0);
Arrays.fill(result, 0);
}
// ================== 演示入口 ==================
public static void main(String[] args) {
// 构造一棵树：
// 1
// / \
// 2 3
// / \ \
// 4 5 6
// /
// 7
// |
// 8
int N = 8;
TreeDifference tree = new TreeDifference(N, 1);
tree.addEdge(1, 2);
tree.addEdge(1, 3);
tree.addEdge(2, 4);
tree.addEdge(2, 5);
tree.addEdge(3, 6);
tree.addEdge(4, 7);
tree.addEdge(7, 8);
tree.prepare();
// 给路径 4 -> 6 上的所有点权 +10
tree.addPathPoint(4, 6, 10);
// 给路径 5 -> 8 上的每条边 +1
tree.addPathEdge(5, 8, 1);
// 给结点 3 的整棵子树内的所有点 +100
tree.addSubtreePoint(3, 100);
long[] ans = tree.apply();
for (int i = 1; i <= N; i++) {
System.out.println("结点 " + i + " 的最终值：" + ans[i]);
}
}
}
3.1 代码解读
up[k][i]是倍增表，up[0][i]是父结点，up[k][i]是 2^k 个祖先；dfs(u, p)一边遍历一边填充up表和depth数组；addPathPoint实现点差分公式cnt[u]+=v, cnt[v]+=v, cnt[lca]-=v, cnt[parent[lca]]-=v；addPathEdge实现边差分公式cnt[u]+=v, cnt[v]+=v, cnt[lca]-=2v；dfsPushUp自下而上累加差分，得到每个结点的真实”被修改次数”。
3.2 复杂度说明
- 预处理：
dfs时每层O(log n)更新祖先表，总O(n log n)； - 每次修改：O(log n) LCA 查询 + O(1) 差分；
- 累加：O(n) DFS。
四、复杂度分析
| 操作 | 时间复杂度 |
|---|---|
| 构造邻接表 | O(n) |
| LCA 预处理（DFS + 倍增） | O(n log n) |
| 单次点差分 | O(log n) |
| 单次边差分 | O(log n) |
| 单次子树差分 | O(log n) |
| 最终累加 | O(n) |
总空间复杂度 O(n log n)，主要来自 up 表。
五、应用场景
5.1 路径计数类问题
最经典的应用是”路径上的访问次数”。例如，给定 m 条路径 (u_i, v_i)，求每个结点被多少条路径经过。直接用树上差分即可：
for each (u_i, v_i):
addPathPoint(u_i, v_i, 1)
最后 apply 即可，复杂度 O((n + m) log n)。
5.2 路径加值 + 离线查询
如果是”路径加值（多组）+ 离线查询每个点的最终值”，也可以用树上差分：把所有路径操作一次性记录到差分数组，最后做一次 DFS 累加。这个套路比”树剖 + 线段树”要简单得多。
5.3 子树修改
“给子树加值”是最简单的差分形式，可以结合 Euler Tour + BIT 实现更强大的”动态子树加 + 单点查询”版本。
5.4 注意事项
- 差分是静态的：所有操作必须预先收集，再做一次 DFS 累加；如果中间需要查中间结果，必须用在线数据结构（树剖/LCT）；
- 点 vs 边：根据题目明确是修改”点”还是”边”，公式略有不同；
- LCA 必须正确：根的选择不影响结果，但一定要保证 LCA 算法的正确性；
- 负权：差分标记可以为负数，但 final 累加后为正数（与题目要求一致）。
六、总结
树上差分是一种非常优雅的算法思想，它把”区间差分”的延迟应用思想延伸到了树形结构上。配合 LCA 预处理，可以在线性时间内解决大量”路径统计 + 路径修改”类问题。它的优点是实现简单、代码量小、常数小；缺点是不支持在线修改和复杂的混合查询。
掌握树上差分的关键在于理解”为什么 cnt[lca] -= v 与 cnt[parent[lca]] -= v“，即”为什么在祖先链上要做两次减法”。理解了这一点，所有变种（如”边差分”）就都可以自然推导出来。希望本文的原理讲解与代码示例能让你真正掌握它，并在竞赛中灵活运用。
