【解雨臣的算法课】第三课：前缀和与差分——用空间换时间，提前算好别现算
“在墓里，最怕的就是重复走回头路。每进一个墓室都要重新探路？那得浪费多少时间。”
——解雨臣
一、上节课回顾
上一课我们讲了二分答案——猜答案，再验证。
黑瞎子用这招猜机关高度，半小时就找到了机关，而胖子还在摸砖。
胖子：“你们怎么找到的？”
黑瞎子：“二分。”
胖子：“二什么分？”
黑瞎子：“就是……你先猜一个高度，然后验证……”
胖子：“那猜错了呢？”
黑瞎子：“猜错了就再猜。”
胖子：“这不就是瞎猜吗？我也会！”
我：“……”
今天我们讲一个预处理的利器——前缀和与差分。
二、故事引入：解雨臣算机关次数
有一次下斗，我遇到一个机关。
这个机关有 n 个格子排成一排，每个格子有一个数字。我每次操作可以选一段连续的格子，把它们全部 +1。
胖子说：“这还不简单？每次找最左边还没到目标值的格子，然后一直往后加，直到遇到已经到目标值的格子为止。模拟一遍就知道了！”
我说：“模拟一次要 O(n)，如果目标值很大，那不得 O(n \times \text{目标值})？”
胖子：“那就慢慢算呗。”
我：“你算吧。n = 10^5，目标值 = 10^9，你算到明年。”
关键问题：我需要一种方法，能快速知道一个区间内所有数加了多少次。
这就是差分的用武之地。
三、什么是前缀和？
3.1 暴力 vs 前缀和
问题：给定数组 a_1, a_2, ..., a_n，有 q 次询问，每次问 [l, r] 的和。
暴力：每次循环累加，O(n) 一次，总 O(nq)。
前缀和：提前算好前缀和数组 s，其中：
s_i = a_1 + a_2 + ... + a_i
那么：
\text{sum}(l, r) = s_r - s_{l-1}
每次询问 O(1)，总 O(n + q)。
3.2 前缀和的构建
int a[N]; // 原数组
int s[N]; // 前缀和数组
for (int i = 1; i <= n; i++) {
s[i] = s[i-1] + a[i];
}
int sum = s[r] - s[l-1];
注意：通常我们让数组下标从 1 开始，这样 s_0 = 0，避免边界判断。
四、二维前缀和——墓室地图
题目背景
墓室是个 n \times m 的网格，每个格子有宝藏价值。我要多次查询某个矩形区域的总价值。
二维前缀和公式
设 s_{i,j} 表示从 (1,1) 到 (i,j) 的矩形和。
递推公式：
s_{i,j} = s_{i-1,j} + s_{i,j-1} - s_{i-1,j-1} + a_{i,j}
查询矩形 (x_1, y_1) 到 (x_2, y_2)：
\text{sum} = s_{x_2,y_2} - s_{x_1-1,y_2} - s_{x_2,y_1-1} + s_{x_1-1,y_1-1}
代码实现
int n, m, q;
int a[N][N];
int s[N][N];
int main() {
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
}
}
while (q--) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
cout << ans << endl;
}
return 0;
}
五、什么是差分？
5.1 从问题引入
问题：我有 n 个格子，初始都是 0。要进行 m 次操作，每次把 [l, r] 内的所有格子 +1。最后问每个格子被加了多少次？
暴力：每次操作循环 [l, r] 加 1，O(nm)。
差分：用 O(1) 记录操作，最后 O(n) 还原。
5.2 差分的定义
差分数组 d 满足：
d_i = a_i - a_{i-1}
其中 a_0 = 0。
性质：
- 对原数组 a 的 [l, r] 区间 +k，等价于：
d_l += k,\quad d_{r+1} -= k - 还原原数组：a_i = a_{i-1} + d_i，即对 d 求前缀和
5.3 差分模板
int a[N]; // 原数组
int d[N]; // 差分数组
void add(int l, int r, int k) {
d[l] += k;
d[r+1] -= k;
}
void build() {
for (int i = 1; i <= n; i++) {
a[i] = a[i-1] + d[i];
}
}
六、二维差分——墓室里的机关阵
代码实现
int d[N][N];
void add(int x1, int y1, int x2, int y2, int k) {
d[x1][y1] += k;
d[x1][y2+1] -= k;
d[x2+1][y1] -= k;
d[x2+1][y2+1] += k;
}
void build() {
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];
}
}
}
七、经典例题：解雨臣的教室
题目背景
解家的学堂有 n 间教室，每间教室有 r_i 个座位。
有 m 份订单，每份订单要用 d_i 个座位，从第 s_i 天到第 t_i 天。
每天所有订单同时生效。如果某天某个教室座位不够，这个订单就要取消。
问：第一个需要取消的订单是第几个？
代码实现
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m;
int a[N]; // 教室座位
int d[N], l[N], r[N]; // 订单：数量，开始，结束
int c[N]; // 差分数组
bool check(int k) {
memset(c, 0, sizeof(c));
for (int i = 1; i <= k; i++) {
c[l[i]] += d[i];
c[r[i] + 1] -= d[i];
}
int now = 0;
for (int i = 1; i <= n; i++) {
now += c[i];
if (now > a[i]) {
return false;
}
}
return true;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
cin >> d[i] >> l[i] >> r[i];
}
int L = 1, R = m, ans = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (check(mid)) {
L = mid + 1;
} else {
ans = mid;
R = mid - 1;
}
}
if (ans == 0) {
cout << 0 << endl;
} else {
cout << -1 << endl << ans << endl;
}
return 0;
}
八、解雨臣踩过的坑
坑1：下标从0还是从1？
解家箴言：一律从 1 开始，s_0 = 0，省心。
坑2：二维前缀和公式记混
s_{i,j} = s_{i-1,j} + s_{i,j-1} - s_{i-1,j-1} + a_{i,j}
解家箴言：画图！画图！画图！
坑3：差分数组开多大？
区间加 [l, r] 时会修改 d_{r+1}，数组要开到 n+2。
解家箴言：多开 5 到 10 个，保平安。
九、课后习题（解家的考验）
基础题
-
子段和：给定数组 a，求有多少个子区间的和等于 k。（提示：前缀和 + 哈希表）
-
二维子矩阵和：给定 n \times m 的矩阵，q 次询问，每次问一个子矩阵的和。
进阶题
-
解雨臣的灯光：有 n 盏灯排成一排，初始全灭。有 m 次操作，每次把 [l, r] 内的灯翻转。问最后哪些灯是亮的。
-
解雨臣的货物：有 n 个仓库，每个仓库有 a_i 吨货物。每天可以从某个连续区间内运走 1 吨货物（每个仓库每天最多运 1 吨）。问最少需要多少天才能运完？
挑战题
- 解雨臣的激光阵：墓室是 n \times m 的网格，有 k 个激光发射器，每个发射器覆盖一个矩形区域。求被激光覆盖次数最多的点的次数。（$n, m \le 2000$，$k \le 10^5$）
提示：二维差分标记每个矩形，最后求二维前缀和还原。
十、下集预告
“前缀和就像下斗前的准备工作——先把地图画好，把每个墓室的位置标清楚。真正下斗的时候，你就不用再画一遍了。”
——解雨臣
下一课，二分图与匈牙利算法——如何给胖子和黑瞎子分配任务，让他们都满意。
下课。
（本系列课程由解雨臣独家赞助，信友队论坛首发。转载需注明出处。）