前缀和与差分
在算法竞赛或日常工程中，前缀和与差分是极具美感的互逆思想。它们的核心在于视角转换：将高复杂度的“范围/区间处理”巧妙地转化为常数级别的“端点/单点操作”，从而将很多原本需要 $O(N)$ 甚至 $O(N^2)$ 的区间查询或修改任务，直接降至 $O(1)$ 或 $O(\log N)$ 级别。
0. 前缀和思想：从生活实例说起
0.1 物理直觉：断尺子问题
假设你手里有一把尺子，但不巧 0 到 3 厘米的地方断裂不见了，现在的刻度是从 3 厘米开始的。 如果要测量一支铅笔的长度，你可以把铅笔一端对准 3 厘米，另一端正好对准 7 厘米。你会脱口而出：铅笔长度是 $7 - 3 = 4$ 厘米。
在这个简单的减法里，就已经包含了“前缀和思想”的缩影： * 3 厘米：尺子起点的“初始偏移量（基准值）”。 * 7 厘米：从起点一直到铅笔末端的“累计总刻度”（在算法里，这叫前缀和，即 Prefix Sum）。 * 铅笔长度：我们要测量的真实区间值。
$$\text{区间的真实长度} = \text{结束位置的前缀和} - \text{起点位置的前缀和}$$
0.2 动态需求：直播打赏统计
假设主播在直播过程中不断收到打赏： * 第 1 秒：$5$ 元 * 第 2 秒：$3$ 元 * 第 3 秒：$8$ 元 * 第 4 秒：$2$ 元 * 第 5 秒：$6$ 元
如果弹幕里有观众频繁提问： * “第 2 秒到第 5 秒，一共打赏了多少钱？” * “第 4 秒到第 5 秒，一共打赏了多少钱？”
若采用暴力统计，每次询问都要把对应区间内的数加一遍。当提问次数很多，或者查询的区间跨度极长（如第 1 秒到第 10000 秒）时，计算会非常缓慢。
若采用前缀和法，我们提前计算好每个时刻的“累计打赏额”： * 第 1 秒结束，累计：$5$ * 第 2 秒结束，累计：$5 + 3 = 8$ * 第 3 秒结束，累计：$8 + 8 = 16$ * 第 4 秒结束，累计：$16 + 2 = 18$ * 第 5 秒结束，累计：$18 + 6 = 24$
现在，面对任何区间的提问，只需要一次减法即可给出答案： * 查询 2 到 5 秒：用第 5 秒累计值减去第 1 秒累计值 $\to 24 - 5 = 19$ 元。 * 查询 4 到 5 秒：用第 5 秒累计值减去第 3 秒累计值 $\to 24 - 16 = 8$ 元。
无论区间多长，只要有前缀和数组，每次查询都是 $O(1)$，效率得到了极大的飞跃。
1. 一维前缀和
1.1 定义与核心思想
对于给定的数组 $a$（采用 1-based 索引），定义其前缀和数组 $s$ 如下： $s[i]$ 表示原数组 $a$ 中从第 1 个元素到第 $i$ 个元素的总和。 $$s[i] = \sum_{j=1}^{i} a[j]$$
为了消除边界讨论，我们约定 $s[0] = 0$。前缀和数组的递推构造非常简单： $$s[i] = s[i-1] + a[i]$$
💡 空间换时间：我们通过 $O(N)$ 的时间进行预处理，以此换取后续任意区间求和查询的 $O(1)$ 响应。
1.2 核心操作：区间查询
当我们需要查询原数组 $a$ 在闭区间 $[l, r]$ 内所有元素的和时： 因为： $$s[r] = a[1] + a[2] + \dots + a[l-1] + a[l] + \dots + a[r]$$ $$s[l-1] = a[1] + a[2] + \dots + a[l-1]$$
两式相减可得核心查询公式： $$\sum_{j=l}^{r} a[j] = s[r] - s[l-1]$$
为什么推荐使用 1-based 索引？ 如果采用 0-based 索引，当查询区间包含第 0 个元素时（即 $l=0$），公式中的 $s[l-1]$ 会导致下标越界（$s[-1]$），需要专门写
if语句分情况讨论。使用 1-based 索引时，当 $l=1$，$s[l-1]$ 自然指向已经初始化为 0 的 $s[0]$，公式对所有区间都可以完美统一。
1.3 C++ 模板实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
int a[N];
long long s[N]; // 前缀和容易超出 int，推荐用 long long
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
// 预处理前缀和数组，s[0] 默认初始化为 0
for (int i = 1; i <= n; ++i) {
s[i] = s[i-1] + a[i];
}
while (m--) {
int l, r;
cin >> l >> r;
// O(1) 区间求和
cout << s[r] - s[l-1] << "\n";
}
return 0;
}
- 时间复杂度：预处理 $O(N)$，查询单次 $O(1)$，总复杂度 $O(N + M)$。
- 空间复杂度：$O(N)$。
2. 一维差分
如果说前缀和是为“查询”而生，那么差分就是为“修改（尤其是区间批量修改）”而生的技术。
2.1 定义与核心思想
对于给定的数组 $a$，其差分数组 $d$ 定义如下（1-based 索引）： $$d[1] = a[1]$$ $$d[i] = a[i] - a[i-1] \quad (\text{for } i \ge 2)$$
也就是说，差分数组记录的是原数组中相邻元素的差值。 由此易得一个最核心的性质：差分数组的前缀和就是原数组本身。 $$a[i] = \sum_{j=1}^{i} d[j]$$
推导如下： $$\sum_{j=1}^{i} d[j] = d[1] + d[2] + \dots + d[i] = a[1] + (a[2]-a[1]) + \dots + (a[i]-a[i-1]) = a[i]$$
2.2 核心操作：区间修改
假设需要对原数组 $a$ 的闭区间 $[l, r]$ 内的所有元素都加上一个值 $c$。 如果进行暴力修改，单次操作的时间复杂度为 $O(r - l + 1)$。
观察此时差分数组 $d$ 的变化： 1. 对于 $a[l]$，其值增加了 $c$。由于 $d[l] = a[l] - a[l-1]$，$a[l-1]$ 未受影响，因此新差分值 $d'[l]$ 变为： $$d'[l] = (a[l] + c) - a[l-1] = d[l] + c \quad (\text{即 } d[l] \text{ 增加了 } c)$$ 2. 对于区间 $(l, r]$ 内的元素 $a[i]$（$l < i \le r$），其自身与前驱元素都增加了 $c$，新差分值为： $$d'[i] = (a[i] + c) - (a[i-1] + c) = a[i] - a[i-1] = d[i] \quad (\text{保持不变})$$ 3. 对于 $a[r+1]$，其值没有变，但前驱元素 $a[r]$ 增加了 $c$，新差分值为： $$d'[r+1] = a[r+1] - (a[r] + c) = d[r+1] - c \quad (\text{即 } d[r+1] \text{ 减少了 } c)$$ 4. 其他位置的元素与其前驱均无变化，差分值不变。
结论：对原数组 $a$ 的区间 $[l, r]$ 进行加 $c$ 运算，在物理层面上等价于对差分数组 $d$ 执行两次单点操作： $$\begin{cases} d[l] \leftarrow d[l] + c \ d[r+1] \leftarrow d[r+1] - c \end{cases}$$
区间修改复杂度瞬间从 $O(N)$ 降至 $O(1)$。
2.3 从差分还原回原数组
当经历多次区间修改之后，若我们想恢复并查询最终的原数组，只需对差分数组 $d$ 求一遍前缀和即可： 1. 初始构建差分数组 $d[i] = a[i] - a[i-1]$（若初始数组全为 0，则差分数组也默认为全 0）。 2. 每次区间修改 $[l, r]$ 加 $c$：在 $d[l]$ 上加 $c$，在 $d[r+1]$ 上减 $c$。 3. 全部修改结束后，递推还原：$a[i] = a[i-1] + d[i]$。
2.4 C++ 模板实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
long long a[N], d[N];
void add(int l, int r, int c) {
d[l] += c;
d[r + 1] -= c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
// 若初始数组不全为 0：
// for(int i = 1; i <= n; ++i) cin >> a[i];
// for(int i = 1; i <= n; ++i) d[i] = a[i] - a[i-1];
while (m--) {
int l, r, c;
cin >> l >> r >> c;
add(l, r, c); // O(1) 区间修改
}
// 求前缀和还原原数组
for (int i = 1; i <= n; ++i) {
a[i] = a[i-1] + d[i];
}
for (int i = 1; i <= n; ++i) {
cout << a[i] << " ";
}
cout << "\n";
return 0;
}
- 时间复杂度：单次修改 $O(1)$，最终还原 $O(N)$，总复杂度 $O(N + M)$。
- 空间复杂度：$O(N)$。
3. 二维前缀和与二维差分
引入容斥原理（Inclusion-Exclusion Principle），我们将前缀和与差分延伸到二维矩阵空间。
3.1 二维前缀和
3.1.1 定义与递推公式
二维前缀和 $s[i][j]$ 定义为：从左上角 $(1, 1)$ 到右下角 $(i, j)$ 所包围的矩形区域内所有元素的和。 $$s[i][j] = \sum_{x=1}^{i} \sum_{y=1}^{j} a[x][y]$$
根据几何拼凑与容斥原理，大矩形 $s[i][j]$ 可以由其左边、上方的矩形累加，并扣除重叠部分得到： $$s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]$$
+--------------+----+
| | |
| s[i-1][j-1] | | <-- 重叠小矩形（减一次）
| | |
+--------------+----+
| | <-- s[i][j-1] （左边大矩形）
+-------------------+
3.1.2 子矩阵查询
如果需要查询以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩形内所有元素的和： $$\text{Sum}(x_1, y_1, x_2, y_2) = s[x_2][y_2] - s[x_1-1][y_2] - s[x_2][y_1-1] + s[x_1-1][y_1-1]$$
这同样利用了容斥原理，将任意子矩阵求和的复杂度降为 $O(1)$。
3.1.3 C++ 模板实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 1005;
int n, m, k;
int a[N][N];
long long s[N][N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m >> k)) return 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
// 预处理二维前缀和
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
}
while (k--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
long long ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
cout << ans << "\n";
}
return 0;
}
3.2 二维差分
3.2.1 定义与核心公式
我们构造一个二维差分矩阵 $d$，使得原矩阵 $a$ 是 $d$ 的二维前缀和： $$a[i][j] = \sum_{x=1}^{i} \sum_{y=1}^{j} d[x][y]$$
差分矩阵 $d$ 的具体数学递推式为（即二维前缀和公式的逆运算）： $$d[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]$$
3.2.2 核心操作：子矩阵修改
如果我们需要对以 $(x_1, y_1)$ 为左上角、$(x_2, y_2)$ 为右下角的子矩阵内的所有元素都加 $c$： 为了精确地限制增量范围，我们在差分矩阵 $d$ 的四个角点（端点边界）执行如下四项单点修改： $$\begin{cases} d[x_1][y_1] \leftarrow d[x_1][y_1] + c \ d[x_2+1][y_1] \leftarrow d[x_2+1][y_1] - c \ d[x_1][y_2+1] \leftarrow d[x_1][y_2+1] - c \ d[x_2+1][y_2+1] \leftarrow d[x_2+1][y_2+1] + c \end{cases}$$
(x1, y1) [+c] ----------------- (x1, y2+1) [-c]
| |
| |
(x2+1, y1)[-c] ----------------- (x2+1, y2+1)[+c]
这四处修改会在还原前缀和时，完美拼凑并对齐原矩阵中的目标子矩形，且不会影响其他任何区域。
3.2.3 C++ 模板实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 1005;
int n, m, k;
long long a[N][N], d[N][N];
void add(int x1, int y1, int x2, int y2, int c) {
d[x1][y1] += c;
d[x2 + 1][y1] -= c;
d[x1][y2 + 1] -= c;
d[x2 + 1][y2 + 1] += c;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m >> k)) return 0;
// 若初始矩阵不全为 0：
// for(int i=1; i<=n; ++i) {
// for(int j=1; j<=m; ++j) {
// cin >> a[i][j];
// add(i, j, i, j, a[i][j]); // 也可以利用公式直构
// }
// }
while (k--) {
int x1, y1, x2, y2, c;
cin >> x1 >> y1 >> x2 >> y2 >> c;
add(x1, y1, x2, y2, c); // O(1) 矩形增值修改
}
// 二维前缀和还原原矩阵
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + d[i][j];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cout << a[i][j] << " ";
}
cout << "\n";
}
return 0;
}
4. 与高级数据结构的联系：从静态走向动态
上述讨论的差分模型属于“批量离线修改，单次最终查询”。如果面对修改与查询互相交错进行的在线操作，我们每次修改后都要花 $O(N)$ 重构前缀和，整体开销会变得无法承受。 这正是树状数组（Binary Indexed Tree / Fenwick Tree）等动态维护工具施展拳脚的舞台。
4.1 树状数组动态前缀和
树状数组能在 $O(\log N)$ 时间内支持单点修改与前缀和查询：
* add(x, c)：将 $a[x]$ 加上 $c$。
* query(x)：查询前缀和 $\sum_{i=1}^x a[i]$。
有了前缀和查询，区间 $[l, r]$ 求和便可直接表达为：query(r) - query(l - 1)，单次耗时 $O(\log N)$。
4.2 差分与树状数组：单点查询与区间修改的结合
考虑以下动态问题：支持区间修改（$[l, r]$ 全体加 $c$）与单点查询（查询 $a[x]$ 的值）。
我们知道：
1. 区间修改等价于对差分数组 $d$ 进行两次单点更新：add(l, c)，add(r + 1, -c)。
2. 单点查询 $a[x]$ 本质上是差分数组的前缀和：$a[x] = \sum_{i=1}^x d[i]$。
因此，我们只需要用树状数组维护差分数组 $d$，即可将操作效率全部优化至 $O(\log N)$：
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
long long t[N]; // 树状数组，维护差分数组 d
void add(int x, long long c) {
for (; x <= n; x += x & -x) t[x] += c;
}
long long sum(int x) {
long long res = 0;
for (; x > 0; x -= x & -x) res += t[x];
return res;
}
// 区间修改：[l, r] 加 c
void radd(int l, int r, int c) {
add(l, c);
if (r + 1 <= n) add(r + 1, -c);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
// 假设初始不全为0，需要将每个 a[i] 视作区间 [i, i] 的单点修改：
// for(int i=1; i<=n; ++i) {
// long long val; cin >> val;
// radd(i, i, val);
// }
while (m--) {
int op; cin >> op;
if (op == 1) {
int l, r, c;
cin >> l >> r >> c;
radd(l, r, c); // O(log N) 修改
} else {
int x; cin >> x;
cout << sum(x) << "\n"; // O(log N) 查询
}
}
return 0;
}
4.3 双树状数组下的区间修改与区间查询
如果问题更进一步，在线同时支持：区间修改 与 区间查询（$[l, r]$ 区间求和） 呢？ 区间和可以转换为两个前缀和相减。我们需要求解 $\sum_{k=1}^x a[k]$。 因为 $a[k] = \sum_{i=1}^k d[i]$，我们将式子展开并重新整理： $$\sum_{k=1}^{x} a[k] = \sum_{k=1}^{x} \sum_{i=1}^{k} d[i]$$
分析每一项 $d[i]$ 的贡献，它总共会在 $a[i], a[i+1], \dots, a[x]$ 中出现，共计出现了 $x - i + 1$ 次。因此： $$\sum_{k=1}^{x} a[k] = \sum_{i=1}^{x} (x - i + 1) \cdot d[i]$$ $$\sum_{k=1}^{x} a[k] = (x + 1) \sum_{i=1}^{x} d[i] - \sum_{i=1}^{x} (i \cdot d[i])$$
这个数学变形非常美妙，它将前缀和转变成了两个经典的前缀和查询： 1. $\sum_{i=1}^x d[i]$：差分数组 $d$ 的前缀和。 2. $\sum_{i=1}^x (i \cdot d[i])$：新数组 $d'[i] = i \cdot d[i]$ 的前缀和。
我们可以使用两个树状数组分别进行维护： * $t_1$：维护 $d[i]$。 * $t_2$：维护 $i \cdot d[i]$。
C++ 代码实现
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
long long t1[N], t2[N]; // t1 维护 d[i]，t2 维护 i * d[i]
void add(long long t[], int x, long long c) {
for (; x <= n; x += x & -x) t[x] += c;
}
long long sum(long long t[], int x) {
long long res = 0;
for (; x > 0; x -= x & -x) res += t[x];
return res;
}
void radd(int l, int r, long long c) {
add(t1, l, c);
add(t1, r + 1, -c);
add(t2, l, l * c);
add(t2, r + 1, -(r + 1) * c);
}
// 查询 a[1...x] 的前缀和
long long psum(int x) {
if (x == 0) return 0;
long long s1 = sum(t1, x);
long long s2 = sum(t2, x);
return (x + 1) * s1 - s2;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
long long prev = 0;
for (int i = 1; i <= n; ++i) {
long long cur; cin >> cur;
radd(i, i, cur - prev); // 初始值导入
prev = cur;
}
while (m--) {
int op; cin >> op;
if (op == 1) {
int l, r; long long c;
cin >> l >> r >> c;
radd(l, r, c);
} else {
int l, r;
cin >> l >> r;
cout << psum(r) - psum(l - 1) << "\n";
}
}
return 0;
}
5. 树上的差分艺术
差分思想并不局限于一维或二维线性结构，在树形结构中也大放异彩。主要分为子树修改与路径修改。
5.1 子树修改与查询
对树进行 DFS 时，我们可以记录下每个节点 $u$ 的进入时间戳 $tin[u]$ 与离开时间戳 $tout[u]$。 这就是树的 DFS 序（或称为 Euler Tour）。 一个至关重要的性质是：节点 $u$ 的子树中的所有节点，其时间戳都在线性闭区间 $[tin[u], tout[u]]$ 之中。
对子树 $u$ 内所有节点加 $c$，便完全等价于在线性 DFS 序数组上进行一维区间修改 $[tin[u], tout[u]]$： * 修改：$d[tin[u]] \leftarrow d[tin[u]] + c$, $d[tout[u]+1] \leftarrow d[tout[u]+1] - c$。 * 还原：修改完毕后，在线性数组上求前缀和，即可完美映射回树中各个节点的真实值。
#include <iostream>
#include <vector>
using namespace std;
const int N = 100005;
int n, m;
vector<int> g[N];
int in[N], out[N], timer;
long long d[N]; // 差分数组，基于 DFS 序
long long val[N]; // 还原后的节点值
void dfs(int u, int p) {
in[u] = ++timer;
for (int v : g[u]) {
if (v == p) continue;
dfs(v, u);
}
out[u] = timer;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
dfs(1, 0); // 预处理 DFS 序
while (m--) {
int u, c;
cin >> u >> c;
d[in[u]] += c;
if (out[u] + 1 <= n) {
d[out[u] + 1] -= c;
}
}
// 线性求前缀和
for (int i = 1; i <= n; ++i) {
d[i] += d[i - 1];
}
// 映射回原树节点
for (int i = 1; i <= n; ++i) {
val[i] = d[in[i]];
cout << val[i] << " ";
}
cout << "\n";
return 0;
}
5.2 路径修改与查询
如果我们需要将树上两点 $u, v$ 之间简单唯一路径上的所有节点都加上 $c$。 为了避开高代价的路径遍历，我们将“路径修改”转换为“差分标记”。
设 $l = \text{lca}(u, v)$ 为 $u, v$ 的最近公共祖先（LCA），我们可以对差分数组 $d$ 进行如下单点标记操作： $$\begin{cases} d[u] \leftarrow d[u] + c \ d[v] \leftarrow d[v] + c \ d[l] \leftarrow d[l] - c \ d[\text{parent}(l)] \leftarrow d[\text{parent}(l)] - c \end{cases}$$
在此差分模型下，每个节点的真实值定义为其子树内所有差分值的总和： $$\text{Value}(u) = \sum_{v \in \text{subtree}(u)} d[v]$$
核心原理解析：
- $d[u] += c$：使从 $u$ 到根节点路径上的所有节点都累计增加 $c$。
- $d[v] += c$：使从 $v$ 到根节点路径上的所有节点都累计增加 $c$。
- $d[l] -= c$：此时从 $l$ 到根的重合祖先路径被多加了一次，在此减去一个 $c$。
- $d[\text{parent}(l)] -= c$：由于 $l$ 本身在路径上应该被加一次，但 $l$ 之外的祖先部分（即 $\text{parent}(l)$ 及以上）不能被波及，因此我们在其父节点处再扣除一次 $c$。
修改完成后，自底向上进行一次 DFS 子树累加即可。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005, LOGN = 18;
int n, m;
vector<int> g[N];
long long d[N];
int dep[N], fa[N][LOGN];
void dfs1(int u, int p) {
dep[u] = dep[p] + 1;
fa[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (int v : g[u]) {
if (v == p) continue;
dfs1(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = LOGN - 1; i >= 0; --i) {
if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
}
if (u == v) return u;
for (int i = LOGN - 1; i >= 0; --i) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
// DFS 子树求和还原
void dfs2(int u, int p) {
for (int v : g[u]) {
if (v == p) continue;
dfs2(v, u);
d[u] += d[v]; // 子树差分和累加到父节点
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> m)) return 0;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
dfs1(1, 0); // 预处理 LCA 倍增数组
while (m--) {
int u, v; long long c;
cin >> u >> v >> c;
int l = lca(u, v);
d[u] += c;
d[v] += c;
d[l] -= c;
if (fa[l][0] != 0) d[fa[l][0]] -= c;
}
dfs2(1, 0); // 差分还原
for (int i = 1; i <= n; ++i) {
cout << d[i] << " ";
}
cout << "\n";
return 0;
}
6. 核心精髓与避坑指南
6.1 运算的对偶性：求和与求差
前缀和与差分本质是一对互逆的操作，正如连续数学中的微积分。 * 前缀和 $\sim$ 积分：将局部变动进行全局累积，获得总量。 * 差分 $\sim$ 微分：测量相邻两个状态之间的瞬时变化率。
区间修改较为繁重时，通过求微分（差分）降低运算维度；区间求和较为繁重时，通过求积分（前缀和）获取瞬时响应。
6.2 常见实践陷阱
- 下标处理：切记强烈建议采用 1-based 索引，并将边界 $s[0]$ 或 $s[0][0]$ 默认置为 0，这能帮你省去大量复杂的逻辑判断。
- 整型溢出（Overflow）：千万小心，和的增长速度是爆发性的。$10^5$ 个 $10^9$ 级别的数累加，会瞬间冲爆常规 32 位整型（
int）。养成使用long long存储前缀和及差分值的习惯。 - 忘记还原：使用差分法解决问题时，最常见的粗心是在写完修改后，忘记在尾部进行最终的前缀和重构计算。差分数组本身并不是最终答案，求出其前缀和才能得到原数组。
- 数位和越界边界：进行二维差分修改 $d[x_2+1][y_2+1]$ 时，很容易出现 $x_2+1 > n$ 的越界情况。在分配容器大小时，数组必须习惯性开大一点（通常为
N + 2或N + 5），以确保越界操作安全。
7. 经典例题选讲
例题 1：P3128 [USACO15DEC] Max Flow P (树上差分)
题目描述
在 $N$（$2 \le N \le 50,000$）个牛棚之间有 $N-1$ 条管道相连，管道相互连通。 有 $K$（$1 \le K \le 100,000$）条牛奶泵送路径，第 $i$ 条路径起终点分别为 $s_i$ 和 $t_i$。每条路径泵送都会对经过的牛棚产生 1 单位的流量。求路径全部泵送完后，承受流量最大的单个牛棚所承载的流量。
题解思路
这是一个极为经典的树上路径批量增值、单次最后求最值问题，可以直接套用路径树上差分模型。 1. 使用倍增法预处理出树上所有节点的深度与 LCA 关系。 2. 每次修改 $s \to t$ 流量加 1： $$d[s]++, \quad d[t]++, \quad d[\text{lca}(s, t)]--, \quad d[\text{parent}(\text{lca}(s, t))]--$$ 3. 最终通过一次自底向上的回溯 DFS 累加子树差分值恢复数据。 4. 遍历所有节点的值获取全局最大值。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 50005, LOGN = 18;
int n, k;
vector<int> g[N];
int dep[N], fa[N][LOGN];
int d[N]; // 差分数组
void dfs1(int u, int p) {
dep[u] = dep[p] + 1;
fa[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (int v : g[u]) {
if (v == p) continue;
dfs1(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = LOGN - 1; i >= 0; --i) {
if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
}
if (u == v) return u;
for (int i = LOGN - 1; i >= 0; --i) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
void dfs2(int u, int p) {
for (int v : g[u]) {
if (v == p) continue;
dfs2(v, u);
d[u] += d[v]; // 回溯时子树向上合并
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (!(cin >> n >> k)) return 0;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
dfs1(1, 0); // 预处理 LCA
for (int i = 0; i < k; ++i) {
int u, v; cin >> u >> v;
int l = lca(u, v);
d[u]++;
d[v]++;
d[l]--;
if (fa[l][0] != 0) d[fa[l][0]]--;
}
dfs2(1, 0); // 还原数据
int ans = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, d[i]);
}
cout << ans << "\n";
return 0;
}
例题 2：P1438 无聊的数列 (线性函数变换法)
题目描述
维护一个数列 $a_i$，需要动态支持以下两类在线操作：
1. 1 l r K D：给区间 $[l, r]$ 整体增加一个等差数列。首项为 $K$，公差为 $D$。也就是说，$a[l] \leftarrow a[l] + K$，$a[l+1] \leftarrow a[l+1] + K + D$，以此类推。
2. 2 p：在线询问单点第 $p$ 个数的值 $a_p$。
题解思路
本题要解决的关键在于：给一个区间增加一个等差数列。 我们可以对区间内的任意一个坐标 $i$（$l \le i \le r$），计算其增加的值： $$\text{added_value}(i) = K + (i - l) \times D$$
我们对其进行代数变形，整理为经典线性函数格式： $$\text{added_value}(i) = D \cdot i + (K - l \cdot D)$$
这个代数变形具有决定性意义，它告诉我们：区间加一个等差数列，等价于对区间内的每一个点 $i$，加上一个斜率为 $D$、常数项为 $K - l \cdot D$ 的线性函数。 我们可以将问题完美拆分成两个独立的部分： 1. 斜率维护部分：对区间 $[l, r]$ 每个点 $i$，其对应的值增加 $D \cdot i$。 2. 常数项维护部分：对区间 $[l, r]$ 每个点 $i$，其对应的值增加常数 $C = K - l \cdot D$。
查询任意位置 $p$ 上的总累积增量时，只需要累加所有覆盖了 $p$ 点的斜率和常数即可： $$\text{delta}[p] = \sum (D_j \cdot p + C_j) = p \cdot \left(\sum D_j\right) + \left(\sum C_j\right)$$
这被巧妙地降维转换成了两个“区间修改、单点查询”的经典问题： 1. 用第一个树状数组 $f_b$（维护斜率差分）来管理覆盖点 $p$ 的总斜率 $\sum D_j$。 2. 用第二个树状数组 $f_c$（维护常数项差分）来管理覆盖点 $p$ 的总常数项 $\sum C_j$。
对于等差数列操作 1 l r K D，执行区间差分修改：
* 更新常数项 $C = K - l \cdot D$：fc.add(l, C), fc.add(r + 1, -C)
* 更新斜率 $D$：fb.add(l, D), fb.add(r + 1, -D)
单点 $p$ 处的最终答案： $$a_{\text{final}}[p] = a_{\text{initial}}[p] + f_c.\text{sum}(p) + p \cdot f_b.\text{sum}(p)$$
代码实现
#include <iostream>
#include <vector>
using namespace std;
// 树状数组结构，维护基础差分
struct BIT {
vector<long long> t;
int n;
BIT(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
t.assign(n + 1, 0);
}
void add(int x, long long v) {
for (; x <= n; x += x & -x) t[x] += v;
}
long long sum(int x) {
long long s = 0;
for (; x > 0; x -= x & -x) s += t[x];
return s;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<long long> a(n + 2, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
// fc 维护常数项 C 的差分，fb 维护斜率 D 的差分
BIT fc(n + 1), fb(n + 1);
while (m--) {
int op; cin >> op;
if (op == 1) {
int l, r; long long k, d;
cin >> l >> r >> k >> d;
long long c = k - l * d;
// 对区间 [l, r] 增值常数项 c
fc.add(l, c);
fc.add(r + 1, -c);
// 对区间 [l, r] 增值斜率项 d
fb.add(l, d);
fb.add(r + 1, -d);
} else {
int p; cin >> p;
// 还原答案：a_p + sum_C + p * sum_D
long long res = a[p] + fc.sum(p) + p * fb.sum(p);
cout << res << "\n";
}
}
return 0;
}
—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com
