树上点差分算法详解

1. 什么是树上点差分树上点差分是一种基于树形结构通常是无根树的差分算法用于高效处理树上路径上的点权更新与查询问题。它是线性差分思想在树上的自然延伸。核心思想是当需要对树上某条简单路径u → v上的所有点的点权进行统一修改如增加某个值时我们可以通过修改路径端点u和v及其最近公共祖先LCA处的差分值将时间复杂度从 O(路径长度) 优化到 O(1)预处理 LCA 后。2. 算法原理与操作假设我们有一棵以节点 1 为根的树每个节点有一个初始点权val[x]。我们维护一个差分数组diff[x]。点权更新操作将路径u → v上的所有节点的点权增加c。设l LCA(u, v)。对差分数组进行如下修改diff[u] cdiff[v] cdiff[l] - c如果l不是根节点则diff[parent[l]] - c最终点权计算通过一次从根节点开始的深度优先搜索DFS进行前缀和还原。void dfs(int u, int fa) { for (int v : tree[u]) { if (v fa) continue; dfs(v, u); diff[u] diff[v]; // 子节点的差分值累加到父节点 } val[u] diff[u]; // 最终点权 初始点权 差分前缀和 }这样所有更新操作完成后一次 DFS 即可得到所有节点的最终点权。3. 代码实现C以下是一个完整的树上点差分实现示例包含 LCA 的倍增预处理。#include iostream #include vector #include cmath using namespace std; const int MAXN 100005; const int LOG 17; vectorint tree[MAXN]; int depth[MAXN]; int parent[MAXN][LOG]; int diff[MAXN]; int val[MAXN]; // 预处理深度和倍增祖先 void dfs_lca(int u, int p) { depth[u] depth[p] 1; parent[u][0] p; for (int i 1; i LOG; i) { parent[u][i] parent[parent[u][i-1]][i-1]; } for (int v : tree[u]) { if (v p) continue; dfs_lca(v, u); } } // 查询 LCA int lca(int u, int v) { if (depth[u] depth[v]) swap(u, v); int diff_depth depth[u] - depth[v]; for (int i 0; i LOG; i) { if (diff_depth i 1) { u parent[u][i]; } } if (u v) return u; for (int i LOG-1; i 0; i--) { if (parent[u][i] ! parent[v][i]) { u parent[u][i]; v parent[v][i]; } } return parent[u][0]; } // 点差分更新操作 void point_update(int u, int v, int c) { int l lca(u, v); diff[u] c; diff[v] c; diff[l] - c; if (parent[l][0] ! 0) { // 如果 l 不是根节点假设根为1 diff[parent[l][0]] - c; } } // 最终点权计算 DFS void dfs_calc(int u, int p) { for (int v : tree[u]) { if (v p) continue; dfs_calc(v, u); diff[u] diff[v]; } val[u] diff[u]; } int main() { int n, m; cin n m; // 建树 for (int i 1; i n; i) { int u, v; cin u v; tree[u].push_back(v); tree[v].push_back(u); } // 初始化点权假设初始为0 for (int i 1; i n; i) val[i] 0; // 预处理 LCA以1为根 depth[0] -1; dfs_lca(1, 0); // 执行 m 次点权更新操作 while (m--) { int u, v, c; cin u v c; point_update(u, v, c); } // 计算最终点权 dfs_calc(1, 0); // 输出结果 for (int i 1; i n; i) { cout val[i] ; } cout endl; return 0; }4. 应用场景与例题典型应用树上路径点权更新如“给树上一条路径的所有节点增加一个值”。多次更新后单点/全局查询所有更新操作完成后查询每个节点的最终点权。结合其他算法与树链剖分、树上启发式合并等结合解决更复杂问题。例题洛谷 P3128 [USACO15DEC] Max Flow题目大意给定一棵树有K次操作每次操作给定两个节点u, v将u到v路径上的所有点的点权加 1。所有操作完成后问点权最大的节点的点权是多少。这正是树上点差分的模板题。使用上述算法时间复杂度为O((NK) log N)LCA 预处理 O(N log N)每次更新 O(log N)。5. 时间复杂度分析预处理DFS 求深度和倍增数组O(N log N)。单次更新求 LCA O(log N)修改差分数组 O(1)。最终计算一次 DFS 还原点权O(N)。总复杂度O(N log N K log N N)通常简化为 O((NK) log N)。6. 总结树上点差分是将差分思想从线性序列推广到树形结构的经典算法它通过巧妙的差分标记将路径上的区间更新转化为常数次端点修改再通过一次 DFS 前缀和还原。掌握该算法需要理解差分数组diff[]的定义与物理意义。LCA 在确定路径端点影响范围时的关键作用。DFS 还原时差分值从子节点向父节点累加的过程。该算法是解决树上路径点权更新问题的利器也是学习树上边差分、树链剖分等高级技巧的重要基础。