基础算法：差分（Difference Array）
在前缀和算法中，我们学习了如何通过预处理在 $O(1)$ 的时间复杂度内求出某一个区间的元素之和。而在实际的算法应用中，我们常常会遇到另一种高频操作：频繁地将某一个区间内的所有元素统一加上或减去一个特定的值。
如果使用暴力遍历，每次区间修改的时间复杂度都是 $O(N)$，面对海量数据和高频操作时必然会超时。此时，我们就需要引入前缀和的“逆运算”——差分（Difference Array）。
与前缀和的核心思想一致，差分同样是经典的用空间替换时间的做法，它可以在暴力枚举的过程中，快速给出修改后的结果，从而极大地优化时间复杂度。
个人笔记 / 核心总结：
- 前缀和与差分是一对互逆的运算。
- 差分的核心作用：快速实现将某个区间所有的元素加上一个数的操作，将原本 $O(N)$ 的区间修改操作优化为 $O(1)$ 的时间复杂度。
- ** 避坑指南（进阶提醒）：所有的差分操作，都必须全部执行完毕后，才能通过求前缀和还原出操作之后的数组。如果题目要求“执行若干次修改后，立刻查询一次，然后再继续执行修改”，此时极不推荐使用差分！遇到这种“边修改边查询”的动态需求，应该使用线段树（Segment Tree）** 或 树状数组（Fenwick Tree） 来完成。
一、 一维差分
1. 核心思路与原理
假设我们有一个原数组 $a$，我们需要构造一个差分数组 $f$。
差分数组的定义：差分数组中的每一项表示当前元素与前一个元素的差值，即：
$$f[i] = a[i] - a[i-1]$$
展开来看：
$$f[1] = a[1]$$
$$f[2] = a[2] - a[1]$$
$$f[3] = a[3] - a[2]$$
$$...$$
如何通过差分数组还原原数组？
根据定义，对差分数组求一次前缀和，就可以无损还原出原数组：
$$a[1] = f[1]$$
$$a[2] = a[2] - a[1] + a[1] = f[2] + f[1]$$
$$a[3] = a[3] - a[2] + a[2] - a[1] + a[1] = f[3] + f[2] + f[1]$$
推导至通用公式：
$$a[i] = f[i] + f[i-1] + f[i-2] + ... + f[1]$$
2. 区间修改的推导过程
假设我们要对原数组 $a$ 的 $[L, R]$ 区间内的所有元素统一加上 $k$。
如果直接操作原数组，需要遍历 $[L, R]$，非常耗时。但在差分数组 $f$ 中，情况会变成怎样？
- $L$ 位置的元素增加了 $k$，而 $L-1$ 位置的元素不变。因此，它们之间的差值增加了 $k$，即：$f[L] += k$。
- $L$ 到 $R$ 之间的元素全都增加了 $k$，它们之间的相对差值保持不变，因此差分数组在 $[L+1, R]$ 区间内的值不需要做任何修改。
- $R+1$ 位置的元素没有增加，而 $R$ 位置的元素增加了 $k$。因此，$R+1$ 位置与 $R$ 位置的差值减少了 $k$，即：$f[R+1] -= k$。
- $R+1$ 之后的元素相对差值依然不变。
结论：对原数组 $[L, R]$ 区间的全部加 $k$ 操作，在差分数组中仅仅转化为两步 $O(1)$ 的单点修改：
$$f[L] += k$$
$$f[R+1] -= k$$
💡 个人笔记 / 核心总结：创建差分数组的两种姿势
- 方式一（基于定义）：
f[i] = a[i] - a[i-1]。这种方式需要用到前一个元素a[i-1]，因此必须先完整读取并保留原始数组 $a$。- 方式二（基于性质，强烈推荐）：无需创建和存储原始数组！我们可以把初始数组看作是一个全 0 的数组，在 $i$ 位置读入数据 $a[i]$，等价于对区间 $[i, i]$ 进行了一次区间加 $a[i]$ 的操作。直接套用公式：
f[i] += a[i]; f[i+1] -= a[i];。代码更简洁，还能省下一份空间！
3. 实战演练：【模板】差分
【题目描述】
给你一个长度为 $n$ 的正数数组 $a_1, a_2, ..., a_n$。接下来对这个数组进行 $m$ 次操作，每个操作包含三个参数 $l, r, k$，代表将数组 $a_l, a_{l+1}, ..., a_r$ 都加上 $k$。请输出操作后的数组。
【输入描述】
第一行包含两个整数 $n$ 和 $m$。
第二行包含 $n$ 个整数表示 $a_1, a_2, ..., a_n$。
接下来是 $m$ 行，每行三个整数，分别代表每次操作的参数 $l, r, k$。
（数据范围：$1 \le n, m \le 10^5$, $-10^9 \le a[i], k \le 10^9$）
【输出描述】
输出 1 行，表示 $m$ 次操作后的 $a_1, a_2, ..., a_n$。
【正确代码】
#include <iostream>using namespace std;typedef long long LL;
const int N = 1e5 + 10;int n, m;
LL f[N]; // 差分数组int main()
{cin >> n >> m;// 💡 利用差分数组的性质，以O(1)的方式边读入边创建差分数组（省去原数组空间）for(int i = 1; i <= n; i++){LL x; cin >> x;f[i] += x;f[i+1] -= x;}// 处理 m 次区间修改操作while(m--){LL l, r, k; cin >> l >> r >> k;f[l] += k;f[r+1] -= k;}// 还原出原始的数组：对差分数组做一次前缀和for(int i = 1; i <= n; i++){f[i] = f[i-1] + f[i];cout << f[i] << " ";}return 0;
}
4. 经典应用：海底高铁 (洛谷 P3406)
【题目描述】
该铁路经过 $N$ 个城市。乘车每经过两个相邻的城市之间，必须单独购买这一小段的车票。第 $i$ 段铁路连接了城市 $i$ 和 $i+1$。第 $i$ 段铁路购买纸质单程票需要 $A_i$ 元。
此外还可以花 $C_i$ 元买一张 IC 卡，然后乘坐这段铁路一次只要扣 $B_i (B_i < A_i)$ 元。
Uim 需要出差，从城市 $P_1$ 出发按照 $P_1, P_2, ..., P_M$ 的顺序访问，求出差结束后，至少会花掉多少钱。
【核心思路与原理】
想要求最小花费，核心是需要知道每一段高铁被乘坐了多少次，记作 $cnt[i]$。
对于第 $i$ 段铁路，最小花费就是「买单程票的花费」与「买卡的花费」两者之间的最小值：
$$min_cost = \min(A_i \times cnt[i], B_i \times cnt[i] + C_i)$$
如何求出每一段被乘坐的次数？对于任意一次从 $P_i$ 到 $P_{i+1}$ 的旅行，我们会乘坐区间 $[\min(P_i, P_{i+1}), \max(P_i, P_{i+1}) - 1]$ 内的高铁。
这本质上就是一个将区间内所有数字统一加 1 的操作，完美契合差分数组的应用场景！
【详细推导过程】
- 创建一个全为 0 的差分数组 $f$。
- 遍历访问序列，对于每一次访问（假设从小到大为 $x$ 到 $y$），也就是 $[x, y-1]$ 区间加 1：
$$f[x]++$$
$$f[y]--$$ - 对差分数组做一次前缀和，得到每个路段真实乘坐的次数。
- 遍历每一段，计算局部最优解并累加。
【正确代码】
#include <iostream>
#include <algorithm>using namespace std;typedef long long LL;
const int N = 1e5 + 10;int n, m;
LL f[N]; // 差分数组，记录每一段被乘坐的次数int main()
{cin >> n >> m;int x; cin >> x;for(int i = 2; i <= m; i++){int y; cin >> y;// 保证 x 是起点，y 是终点int start = min(x, y);int end = max(x, y);// 区间 [start, end - 1] 乘坐次数 + 1f[start]++;f[end]--;x = y; // 更新起点为下一次的出发点}// 利用前缀和还原出原数组（各段铁路的乘坐总次数）for(int i = 1; i <= n; i++) {f[i] += f[i - 1];}// 计算总最小花费LL ret = 0;for(int i = 1; i < n; i++){LL a, b, c; cin >> a >> b >> c;ret += min(a * f[i], c + b * f[i]);}cout << ret << endl;return 0;
}
二、 二维差分
一维差分解决的是一维数组的区间增减问题，那么二维差分矩阵解决的就是：快速处理将二维数组中，某一个子矩阵内所有元素统一加上一个数的操作。
1. 核心思路与推导过程
假设我们需要将原始矩阵 $a$ 中，以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩阵的每个元素都加上 $k$。
如果在二维差分矩阵 $f$ 的 $(x_1, y_1)$ 位置加上 $k$：
$$f[x_1][y_1] += k$$
当我们对这个差分矩阵求二维前缀和时，这个 $+k$ 的影响会波及到 $(x_1, y_1)$ 到整个矩阵右下角的全部区域。
为了将影响严格限制在 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的子矩阵内，我们需要“抵消”掉溢出区域的效应（结合容斥原理）：
- 抵消下方多余的区域：从 $(x_2+1, y_1)$ 开始的区域不需要加 $k$，因此：
$$f[x_2+1][y_1] -= k$$ - 抵消右侧多余的区域：从 $(x_1, y_2+1)$ 开始的区域不需要加 $k$，因此：
$$f[x_1][y_2+1] -= k$$ - 补回多减的右下方区域：上述两步操作中，$(x_2+1, y_2+1)$ 到右下角的区域被多减了一次，需要加回来：
$$f[x_2+1][y_2+1] += k$$
结论：二维差分矩阵的单次子矩阵修改仅需 4 步 $O(1)$ 操作：
$$f[x_1][y_1] += k$$
$$f[x_1][y_2+1] -= k$$
$$f[x_2+1][y_1] -= k$$
$$f[x_2+1][y_2+1] += k$$
还原二维原始矩阵：
对差分矩阵做一次完整的二维前缀和即可：
$$f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j]$$
2. 实战演练：【模板】二维差分
【题目描述】
给你一个 $n$ 行 $m$ 列的矩阵。接下来有 $q$ 次操作，每次输入 5 个参数 $x_1, y_1, x_2, y_2, k$，表示把以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩阵的每个元素都加上 $k$。请输出操作后的矩阵。
【正确代码】
#include <iostream>using namespace std;typedef long long LL;
const int N = 1010;int n, m, q;
LL f[N][N]; // 差分矩阵// 封装二维差分的核心逻辑
void insert(int x1, int y1, int x2, int y2, LL k)
{f[x1][y1] += k; f[x1][y2 + 1] -= k; f[x2 + 1][y1] -= k;f[x2 + 1][y2 + 1] += k;
}int main()
{cin >> n >> m >> q;// 💡 预处理差分矩阵：读入数据点 (i, j) = x 等价于在子矩阵 [(i,j), (i,j)] 上加 xfor(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){LL x; cin >> x;insert(i, j, i, j, x);}}// 处理 q 次矩阵修改操作while(q--){LL x1, y1, x2, y2, k; cin >> x1 >> y1 >> x2 >> y2 >> k;insert(x1, y1, x2, y2, k);}// 利用二维前缀和还原出修改之后的数组for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}
3. 经典应用：地毯 (洛谷 P3397)
【题目描述】
在 $n \times n$ 的格子上有 $m$ 个地毯。给出这些地毯的信息（左上角和右下角坐标），问每个点被多少个地毯覆盖。
【核心思路与原理】
由于每次铺地毯都是在二维矩阵的一个子区域（矩形范围）内统一累加 1 次覆盖次数，这毫无疑问是二维差分的标准应用场景。
初始矩阵全为 0，每读入一个地毯坐标，就调用一次二维差分的 insert(x1, y1, x2, y2, 1)。最终做一次二维前缀和还原覆盖次数即可。
【正确代码】
#include <iostream>using namespace std;const int N = 1010;
int n, m;
int f[N][N]; // 差分矩阵// 差分数组的性质
void insert(int x1, int y1, int x2, int y2, int k)
{f[x1][y1] += k; f[x1][y2+1] -= k; f[x2+1][y1] -= k; f[x2+1][y2+1] += k;
}int main()
{cin >> n >> m;// 构建差分数组，初始背景为全0，直接叠加密度while(m--){int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;insert(x1, y1, x2, y2, 1);}// 利用前缀和还原修改之后的数组for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}
声明：本博客由gemini基于laobie本地obsidian笔记转写，意在将obsidian内置图片转化为了纯文本或表格描述，便于博客上传