章节概述
差分是前缀和的逆运算。前缀和用于快速区间求和，差分用于快速区间修改。
两者配合使用覆盖了大量数组操作的高效实现。
核心原理
1. 一维差分 — 区间修改 O(1)
给定数组 a[1..n]，定义差分数组 d 满足: a 是 d 的前缀和，即:
等价于: （其中 ）
区间修改公式:
对 a[l..r] 全部加上 x:
d[l] += x
d[r+1] -= x
修改完成后求一次前缀和即可得到新数组。修改 O(1)，恢复 O(n)。
2. 二维差分 — 子矩阵修改 O(1)
对矩形 (x1,y1) 到 (x2,y2) 加上 x:
diff[x1][y1] += x
diff[x1][y2+1] -= x
diff[x2+1][y1] -= x
diff[x2+1][y2+1] += x
原理: 前缀和传递，四个角通过容斥达到只对目标矩形内生效的效果。
3. IncDec 问题的数学优化
区间 ±1 操作等价于对差分数组两个端点操作。目标使 d[2..n] 全为 0:
- 最少操作次数 = max(正数和, 负数绝对值之和)
- 可能种数 = |正数和 - 负数绝对值之和| + 1
关键数据结构
- A_容器_Container — vector 存储差分数组
- 前缀和 — 差分逆运算，配合使用
一维差分
#include <iostream>
using namespace std;
const int N = 100005;
int d[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1, x; i <= n; i++) {
cin >> x;
d[i] += x;
d[i + 1] -= x;
}
while (m--) {
int l, r, x;
cin >> l >> r >> x;
d[l] += x;
d[r + 1] -= x;
}
for (int i = 1; i <= n; i++) {
d[i] += d[i - 1];
cout << d[i] << " ";
}
return 0;
}二维差分
#include <iostream>
using namespace std;
const int N = 1005;
int diff[N][N];
int main() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= n; i++)
for (int j = 1, x; j <= m; j++) {
cin >> x;
diff[i][j] += x;
diff[i][j + 1] -= x;
diff[i + 1][j] -= x;
diff[i + 1][j + 1] += x;
}
while (q--) {
int x1, y1, x2, y2, x;
cin >> x1 >> y1 >> x2 >> y2 >> x;
diff[x1][y1] += x;
diff[x1][y2 + 1] -= x;
diff[x2 + 1][y1] -= x;
diff[x2 + 1][y2 + 1] += x;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
cout << diff[i][j] << " ";
}
cout << endl;
}
return 0;
}P3397 地毯
题目: 在 n×n 的网格上铺 m 块矩形地毯，每块地毯覆盖一个矩形区域。求每个格子被覆盖的次数。
思路: 二维差分的经典应用。对每块地毯做 O(1) 差分标记，最后求二维前缀和。
#include <iostream>
using namespace std;
int diff[1005][1005];
int main() {
int n, m;
cin >> n >> m;
while (m--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
diff[x1][y1]++;
diff[x1][y2 + 1]--;
diff[x2 + 1][y1]--;
diff[x2 + 1][y2 + 1]++;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
diff[i][j] += diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1];
cout << diff[i][j] << " ";
}
cout << endl;
}
return 0;
}P4552 [Poetize6] IncDec Sequence
题目: 给定长度为 n 的数列，每次可以选择一个区间 [l,r] 使区间内所有数 +1 或 -1。求最少操作次数使所有数相等，以及最终数列的可能种数。
思路: 问题转化为差分数组 d。设正数之和为 pos，负数绝对值之和为 neg。
最小操作次数 = max(pos, neg)，可能种数 = |pos - neg| + 1。
#include <iostream>
#include <cmath>
using namespace std;
const int N = 100005;
long long a[N], d[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
d[i] = a[i] - a[i - 1];
}
long long pos = 0, neg = 0;
for (int i = 2; i <= n; i++) {
if (d[i] > 0) pos += d[i];
else neg -= d[i];
}
cout << max(pos, neg) << endl;
cout << abs(pos - neg) + 1 << endl;
return 0;
}推荐练习题（洛谷）
相关技巧
多平台练习
| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |