C++ 信奥赛 CSP-S 树上差分算法

1. 树上差分是什么及其作用

定义

树上差分是一种利用差分思想处理树上路径修改问题的算法。它通过对树上节点的差分数组进行操作，将树上路径的修改问题转化为差分数组的修改问题。

作用

1. 高效处理路径修改：在树中，对路径上所有节点进行加/减操作的时间复杂度可优化到 O(logn) 或 O(1)
2. 支持多次修改后统一查询：先进行所有差分操作，最后通过一次 DFS 计算出所有节点的最终值
3. 解决多种问题：
   • 树上点权修改、查询
   • 树上边权修改、查询
   • 覆盖次数统计
   • 最近公共祖先 (LCA) 相关应用

差分思想回顾

在一维数组中，差分数组 diff[i] = arr[i] - arr[i-1]，区间 [l, r]