1. 从一道经典问题说起为什么需要树上差分如果你刷过一些算法题尤其是涉及树形结构和路径修改的题目大概率会遇到这样的场景给你一棵有N个节点的树然后给你M次操作每次操作指定树上的两个节点u和v要求将u到v这条唯一路径上的所有节点或边的权值都加上一个值c。操作全部完成后再询问每个节点或边最终的权值。最朴素的想法是什么对于每次操作都从u走到v沿途给每个节点加上c。一次操作的时间复杂度是O(路径长度)最坏情况是O(N)。M次操作下来就是O(M*N)当N和M都达到10^5级别时这个复杂度是绝对无法接受的。这时我们熟悉的差分思想就可以派上用场了。在线性数组上如果我们想给区间[l, r]的所有元素加上c我们不需要遍历整个区间只需要在差分数组diff上执行diff[l] c和diff[r1] - c最后对diff求前缀和就能得到原数组每个位置被加了多少次。这个技巧将区间修改的复杂度从O(n)降到了O(1)。那么在树这种非线性结构上有没有类似的“区间”修改技巧呢答案是肯定的这就是树上差分。它巧妙地将树上的路径修改转化为对少数几个节点通常是路径的端点和其LCA的差分数组的修改从而将每次路径修改的复杂度从O(路径长度)降至O(1)或O(logN)取决于求LCA的复杂度。树上差分是解决树上路径批量更新、离线查询类问题的利器理解并掌握它能让你在面对许多树形DP、数据结构结合的题目时思路更加清晰。树上差分主要分为两种点差分和边差分。它们的核心思想一脉相承但在差分数组的定义和修改操作上略有不同适用的场景也不同。接下来我们就深入拆解这两种差分方法。2. 核心基石LCA与差分数组的定义在深入差分之前我们必须先理解一个关键概念最近公共祖先。树上差分之所以高效核心就在于它利用了LCA来精确定位路径的“起点”和“终点”。2.1 最近公共祖先的角色对于树上任意两点u和v它们之间的最短路径是唯一的。这条路径可以看作是从u向上走到它们的最近公共祖先lca然后再从lca向下走到v。因此路径u - v可以被拆分为两段u - lca和lca - v。注意lca这个节点在这两段中都被包含了如果考虑点权的话。几乎所有高效的树上差分实现无论是点差分还是边差分其修改操作都会涉及到lca节点有时还包括lca的父节点。因此一个快速求解LCA的算法是必不可少的。常用的有倍增法、树链剖分、Tarjan离线算法等。在竞赛和面试中基于倍增的LCA算法因其实现相对简单、在线查询的特性而被广泛使用。它的预处理复杂度为O(N logN)单次查询复杂度为O(logN)。注意在构思差分方案时一定要在纸上画出u, v, lca的关系图。清晰地看到路径的走向是理解后续差分操作为什么这样设计的关键。很多初学者混淆点差分和边差分的操作就是因为没有在脑中形成清晰的路径模型。2.2 差分数组的载体与初始化在线性差分中我们有一个与原数组等长的diff数组。在树上我们的“原数组”是什么是每个节点的点权或者每条边的边权。那么“差分数组”也需要一个载体。通常我们会定义一个大小也为N1的数组diff或valdiff[x]的初始值为0。它的物理意义是以节点x为根的子树中所有差分值的累加和在后续对diff求“前缀和”时体现。最终我们通过一次后序遍历DFS来从叶子节点向上累加diff值从而得到每个节点或边的真实权值。这里有一个非常重要的理解树上差分的“前缀和”过程实际上是子树和的累加过程。这是因为树的结构决定了信息是从子节点传递到父节点的。3. 点差分详解如何给路径上的所有点加权点差分的目标是对树上u到v的路径上的每一个节点都加上一个值c。3.1 操作公式推导与记忆记住这个经典的操作四联式diff[u] cdiff[v] cdiff[lca] - cdiff[fa[lca]] - c这里fa[lca]表示lca的父节点如果lca是根节点则忽略此操作或不对不存在的父节点操作为什么要这样操作我们来逆向推导一下。 我们的目标是影响u-v路径上的所有点。考虑对diff数组做子树和后一个节点x的最终权值等于其子树内所有diff值之和。diff[u] c这意味着从节点u开始它的所有祖先节点在子树和过程中都会接收到这个c的影响。diff[v] c同理从节点v开始它的所有祖先节点都会接收到这个c的影响。现在影响范围太大了。u和v的公共祖先节点们被加了两次c而路径之外的节点lca的祖先也被加了c。我们需要消除这些多余的影响。diff[lca] - c这个操作是为了消除lca节点被重复加了一次c的影响。因为从u和v来的c都会汇聚到lca使得lca被加了两次而我们只需要加一次所以减掉一次。diff[fa[lca]] - c这个操作是为了阻止c的影响向上扩散到lca的祖先节点。u和v的c影响都会通过lca继续向上传递。我们在lca的父节点处设置一个-c的“屏障”这样当子树和计算到fa[lca]时来自u和v的两个c与这个-c以及可能来自其他子树的-c相互抵消使得lca的祖先节点不受本次路径修改的影响。3.2 一个具体的计算示例假设我们有一棵树1-2-3-4其中1是根。路径是2-4LCA是2。我们要给路径上所有点加1。 节点关系1(根) - 2 - 3 - 4。操作diff[2] 1diff[4] 1diff[lca2] - 1diff[fa[2]1] - 1合并后diff[2]的变化是1 -1 0diff[4] 1diff[1] -1其他节点diff为0。现在进行后序遍历子树和节点4:val[4] diff[4] 1节点3:val[3] diff[3] 子树和 0 val[4] 1节点2:val[2] diff[2] val[3] 0 1 1节点1:val[1] diff[1] val[2] -1 1 0结果路径2-3-4上的节点权值都增加了1val[2]1, val[3]1, val[4]1而节点1的权值不变。符合预期。3.3 点差分的实现模板与注意事项// 假设使用倍增法求LCA, fa[u][k]表示u的2^k级祖先, depth[u]表示深度 // diff[u] 是差分数组 // N 为节点数 void add_path_point(int u, int v, int c) { int lca getLCA(u, v); diff[u] c; diff[v] c; diff[lca] - c; if (fa[lca][0] ! 0) { // 如果lca不是根节点通常根节点编号为1 diff[fa[lca][0]] - c; } } // 最后通过DFS求子树和得到每个点的最终权值val[u] void dfs_sum(int u, int pre) { val[u] diff[u]; for (int v : tree[u]) { if (v pre) continue; dfs_sum(v, u); val[u] val[v]; // 子节点的权值已经包含了其子树的差分和 } } // 调用 dfs_sum(root, 0) 后val[u] 即为节点u的最终权值实操心得在实现时务必注意lca就是根节点的情况。此时fa[lca][0]可能为0或-1表示无父节点。如果不做判断直接diff[fa[lca][0]] - c会导致数组越界。一个安全的做法是如果lca是根就只执行前三步操作。4. 边差分详解如何给路径上的所有边加权边差分的目标是对树上u到v的路径上的每一条边都加上一个值c。边差分有一个常用的技巧将边权下放到深度较大的那个端点。也就是说对于连接父节点p和子节点u的边我们把这条边的权值记录在子节点u上。这样树上除了根节点每个节点都唯一代表了一条从其父节点到它的边。4.1 操作公式推导与记忆在这个模型下对u-v路径上所有边加c等价于对路径上除了LCA节点以外的所有点所代表的边加c。因为LCA节点代表的是其父节点到它的边而这条边并不在u-v的路径上。因此边差分的操作公式比点差分更简洁diff[u] cdiff[v] cdiff[lca] - 2 * c为什么是这样我们同样从子树和的角度理解。diff[u] c和diff[v] c使得从u和v到根节点的路径上的所有边即这些节点的所有祖先边都会收到c的影响。但是u和v的路径只在lca处汇合。从lca到根节点的这段边被u和v的影响各加了一次c总共加了2c而这段边本不应该被修改。diff[lca] - 2 * c这个操作就是在lca处设置一个-2c的抵消项。当计算子树和时这个-2c会沿着父边向上传递正好抵消掉从u和v传来的两个c对lca以上边的影响。而对于lca以下的边即u-lca和v-lca的路径u和v的c影响会保留而lca的-2c影响不会传递下来因为子树和是从下往上的。4.2 一个具体的计算示例同样以树1-2-3-4为例边权下放到子节点。现在给路径2-4上的所有边加1。 节点关系1(根) - 2 - 3 - 4。节点2代表边(1,2)节点3代表边(2,3)节点4代表边(3,4)。操作diff[2] 1diff[4] 1diff[lca2] - 2合并后diff[2]的变化是1 -2 -1diff[4] 1其他节点diff为0。进行后序遍历求子树和注意此时val[u]代表的是节点u所关联的父边的权值节点4:val[4] diff[4] 1(代表边3-4)节点3:val[3] diff[3] val[4] 0 1 1(代表边2-3)节点2:val[2] diff[2] val[3] -1 1 0(代表边1-2)结果路径2-4上的边是 (2-3) 和 (3-4)它们的权值都增加了1。而边(1-2)的权值不变。符合预期因为路径起点是2不包含边1-2。4.3 边差分的实现模板与注意事项// 同样假设已预处理LCA // diff[u] 是差分数组最终val[u]表示节点u与其父节点之间边的权值 void add_path_edge(int u, int v, int c) { int lca getLCA(u, v); diff[u] c; diff[v] c; diff[lca] - 2 * c; } // DFS求子树和得到每条边的权值存储在深度较大的端点val中 void dfs_sum_edge(int u, int pre) { val[u] diff[u]; for (int v : tree[u]) { if (v pre) continue; dfs_sum_edge(v, u); val[u] val[v]; } } // 调用后对于任意非根节点uval[u]就是边(pre, u)的权值。注意事项边差分最后得到的val[u]对于根节点是没有意义的因为根没有父边。在输出答案时通常是从节点2到节点N循环输出val[i]。一定要理解这个“边权下放”模型否则很容易搞混最终答案对应的是哪条边。5. 问题扩展与实战应用场景理解了基础操作我们来看看树上差分能解决哪些复杂问题。5.1 多路径叠加与最大覆盖问题这是树上差分最经典的应用。例如“在树上给出若干条路径求被最多路径覆盖的节点或边是哪几个覆盖次数是多少”解法对每条路径(u, v)使用点差分或边差分操作给diff数组加上1而不是固定的c。所有操作完成后进行一次DFS求子树和。得到的val[u]就是节点u被路径覆盖的次数。然后遍历所有节点求最大值即可。时间复杂度O(N M log N)主要消耗在求M次LCA上。5.2 结合树链剖分进行路径查询树上差分擅长离线的路径修改、最终查询。如果题目要求在线的路径查询例如随时询问某条路径的权值和单纯的差分就不够了需要结合树链剖分和线段树等数据结构。但差分思想依然可以作为优化的一部分。例如有时我们可以用差分来处理批量修改然后用树剖线段树来维护一个基于差分数组的前缀和数据结构以支持快速查询。5.3 逆向思维根据最终状态反推操作有一类问题会告诉你所有操作完成后每个节点或边的权值问你是否存在一系列路径操作能满足这个结果或者求最小操作次数。解法这类问题往往需要逆向思考。我们从叶子节点开始考虑。对于点权如果一个叶子节点u的最终目标权值是target[u]而当前权值是current[u]那么必须有一条以u为一端的路径操作其权值为delta target[u] - current[u]。我们可以利用差分的思想从叶子向根推进不断将所需的变化值delta传递给父节点并检查在根节点处是否所有需求都能被抵消即为0。这实际上是在模拟差分数组求前缀和的逆过程——求差分数组。5.4 结合树上前缀和有时问题不是修改路径而是快速计算路径的权值和。这时可以使用树上前缀和。预处理出从根节点到每个节点u的点权或边权前缀和sum[u]。那么u到v路径的权值和就等于sum[u] sum[v] - 2 * sum[lca] weight[lca]对于点权或者sum[u] sum[v] - 2 * sum[lca]对于边权因为lca点的权值不在路径上。这个技巧常与差分结合一个处理修改一个处理查询。6. 常见错误与调试技巧实录即使理解了原理实现时也难免踩坑。下面是我在多次实践中总结的常见问题。6.1 混淆点差分与边差分的修改公式这是最最常见的错误。记忆口诀点差分u, v加lca减fa[lca]减。四步边差分u, v加lca减2倍。三步调试方法一定要用小样例3-5个节点手工模拟整个差分和求和过程。画图列出每一步操作后的diff数组然后模拟DFS过程计算val数组。这是验证思路和代码最直接有效的方法。6.2 LCA计算错误或未考虑根节点情况如果LCA算错了整个差分修改的目标路径就全错了。确保你的LCA算法经过测试。特别是当u和v相等或者一个是另一个的祖先时算法是否能正确返回。 在点差分中如果lca是根节点fa[lca][0]可能不存在。不处理会导致数组越界或逻辑错误。// 安全的点差分操作 int lca getLCA(u, v); diff[u] c; diff[v] c; diff[lca] - c; if (lca ! root) { // 假设root是根节点编号 diff[parent[lca]] - c; // 使用存储的父节点信息 }6.3 DFS求子树和时遍历顺序错误差分后的求和必须使用后序遍历先递归子节点再处理本节点。因为本节点的最终值依赖于其所有子节点的值之和。如果使用前序或中序结果必然错误。// 正确的后序遍历 void dfs(int u, int pre) { for (int v : tree[u]) { if (v pre) continue; dfs(v, u); // 先递归处理孩子 diff[u] diff[v]; // 再将孩子的差分和累加到父亲 } // 此时diff[u]已经代表了节点u的最终权值点差分 // 对于边差分diff[u]代表的是边(pre, u)的权值但u的最终“点权”无意义 }6.4 数据范围与溢出路径操作次数M和权值c可能很大累加后diff数组的值可能会超出int范围。在竞赛中这通常意味着需要使用long long来定义diff和val数组。6.5 对边权下放模型理解不透彻在边差分问题中输出答案时容易出错。记住val[u]DFS求和后的diff[u]存储的是节点u与其父节点之间那条边的权值。所以最终要输出所有非根节点的val值。如果你错误地输出了根节点的值或者搞反了对应关系答案就错了。一个清晰的实现方式是在DFS求子树和时明确记录父节点。void dfs_edge(int u, int fa) { for (int v : tree[u]) { if (v fa) continue; dfs_edge(v, u); diff[u] diff[v]; // 此时diff[u]已经包含了子节点的信息 } // 遍历结束后对于u ! root, diff[u]就是边(fa, u)的权值 } // 输出for (int i 2; i n; i) cout diff[i] endl;树上差分是一个“思想简单细节致命”的算法。核心的修改公式很短但围绕它的预处理LCA、后续处理DFS求和以及模型转换边权下放却包含了诸多细节。最好的学习方式就是找几道经典的裸题如“运输计划”、“疫情控制”的简化版反复练习亲手推导几个小样例直到能条件反射地区分点和边的差分操作并能在10分钟内写出无bug的代码。当你做到这一点时树上差分就从你的知识库中的一个概念变成了解决树上路径问题的一把顺手利器。