适用对象： 完成第 3 课（二分查找与二分答案）的同学 使用方式： 自学讲义，Dev-C++ 5.11，练习按考场 freopen 格式写 学完本课，你应该能：
问题： 给你 n 个数，要回答 q 次"区间
[l, r] 的和是多少"。暴力做法是每次查询都从 l
加到 r，单次 O(n)，q 次总共 O(nq)——q 一大就超时。
前缀和的思路： 先花 O(n) 预处理出一个数组
preSum，preSum[i] 表示
a[1] + a[2] + ... + a[i]（下标从 1
开始，preSum[0] = 0）。之后任何区间和都能 O(1) 算出来：
sum(l, r) = preSum[r] - preSum[l - 1]道理很简单：preSum[r] 是 1~r
的总和，preSum[l-1] 是 1~(l-1) 的总和，减掉就剩下 l~r。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5;
int a[10] = {0, 3, 1, 4, 1, 5}; // 下标从 1 开始用，a[0] 空着不用
int preSum[10] = {0};
for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + a[i];
cout << preSum[2] - preSum[0] << endl; // a[1]+a[2] = 3+1 = 4
cout << preSum[5] - preSum[2] << endl; // a[3]+a[4]+a[5] = 4+1+5 = 10
return 0;
}📝 复杂度对比： 暴力每次查询 O(n)，q 次查询共 O(n·q)；前缀和预处理 O(n)，之后每次查询 O(1)，共 O(n+q)。当 n、q 都是 10⁵ 级别时，暴力是 10¹⁰ 次运算（超时），前缀和只要 2×10⁵ 次。
⚠️ preSum[0] = 0 是故意留的哨兵，这样
sum(1, r) 也能直接套公式
preSum[r] - preSum[0]，不用特判 l == 1
的情况。
问题： 给你 n 个数，要做 m 次操作，每次把区间
[l, r] 里的每个数都加上 v。暴力做法每次操作
O(r-l+1)，m 次最坏 O(nm)。
差分的思路： 前缀和的"反过来"。构造差分数组
diff[i] = a[i] - a[i-1]（a[0] = 0）。这样
a 数组就是 diff 数组的前缀和。给
[l, r] 整体加 v，只需要改 diff
的两个位置：
diff[l] += v;
diff[r + 1] -= v;道理：diff[l] += v 让"从 l 开始往后"的前缀和都多加了
v；diff[r+1] -= v 把 r+1 之后多加的 v
抵消掉，正好只影响 [l, r]。所有操作做完后，对
diff 求一遍前缀和，就得到修改后的 a 数组。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n = 5;
int diff[10] = {0}; // 初始数组全 0，diff 也全 0
diff[1] += 2; diff[4] -= 2; // [1,3] 整体加 2
diff[2] += 3; diff[5] -= 3; // [2,4] 整体加 3
int a[10] = {0};
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + diff[i];
for (int i = 1; i <= n; i++) cout << a[i] << " ";
cout << endl;
return 0;
}输出：2 5 5 3 0（第 1 个只被第一次操作加到：2；第 2、3
个被两次操作都加到：2+3=5；第 4 个只被第二次操作加到：3；第 5
个没被加到：0）。
⚠️ diff 数组要比 a 数组多开一位。 r
可能等于 n，这时 diff[r+1] 就是
diff[n+1]——数组大小至少要开到
n+2，开小了会越界。
📝 一句话总结： 前缀和解决"区间查询"，差分解决"区间修改"，两者是一对反操作。
给定 n 个数和 q 次查询，每次查询输出区间 [l, r]
的和。
#include <bits/stdc++.h>
using namespace std;
int a[100005], preSum[100005];
int main() {
freopen("range.in", "r", stdin);
freopen("range.out", "w", stdout);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + a[i];
while (q--) {
int l, r;
cin >> l >> r;
cout << preSum[r] - preSum[l - 1] << endl;
}
return 0;
}题意： 一条路可以看成 n 段，第 i 段初始沉降深度为
d[i]。每天可以选一个连续区间
[l, r]，把这个区间里每一段的沉降深度都减
1（要求区间内所有段沉降深度都大于
0）。问最少多少天能把所有段填平（深度都变成 0）。
样例（洛谷 P5019 官方样例）：
输入样例：
6
4 3 2 5 3 5
输出样例：
9思路： "把区间整体减
1"正好是差分的反向操作——用差分数组的眼光看，diff[i] = d[i] - d[i-1]。每次操作选一个区间整体
-1，等价于 diff[l] -= 1, diff[r+1] += 1。要把所有
d[i] 填到 0，只需要把每个"正的差分"用掉——答案就是
diff 数组里所有正数的和：因为每个正的
diff[i]
表示"从这里开始需要新增的填坑量"，这部分不能靠别的操作顺带解决，必须单独起一次操作覆盖到这里。
#include <bits/stdc++.h>
using namespace std;
int d[100005];
int main() {
freopen("road.in", "r", stdin);
freopen("road.out", "w", stdout);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> d[i];
long long ans = 0;
for (int i = 1; i <= n; i++) {
int diff = d[i] - d[i - 1]; // d[0] 默认是 0
if (diff > 0) ans += diff; // 只累加正的差分
}
cout << ans << endl;
return 0;
}样例验证：d = {4,3,2,5,3,5}，差分依次是
4,-1,-1,3,-2,2，正数之和
4+3+2=9，和官方样例一致。
题意： 给定 n 个整数（可能有负数），选一段连续且非空的子段，使这段的和最大，求这个最大和。
样例（洛谷 P1115 官方样例）：
输入样例：
7
2 -4 3 -1 2 -4 3
输出样例：
4（选 [3,5] 段 {3,-1,2}，和为 4。）
思路： 任意子段 [l, r] 的和都是
preSum[r] - preSum[l-1]。要让它最大，preSum[r]
固定时，preSum[l-1]
越小越好——也就是说，边求前缀和，边打擂台记录"目前出现过的最小前缀和"，每一步都算一次"当前前缀和
- 目前最小前缀和"，打擂台更新答案：
#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main() {
freopen("maxsub.in", "r", stdin);
freopen("maxsub.out", "w", stdout);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
long long preSum = 0, minPre = 0, ans = LLONG_MIN;
for (int i = 1; i <= n; i++) {
preSum += a[i];
ans = max(ans, preSum - minPre); // 用目前最小的前缀和更新答案
minPre = min(minPre, preSum); // 更新目前最小的前缀和
}
cout << ans << endl;
return 0;
}这题把 L02 的打擂台和本课的前缀和拼在了一起：minPre
就是一个专门记录"最小前缀和"的擂台冠军。
错误 1：diff 数组开小了，越界
int diff[100005];
// n 最大是 100000，r 最大是 100000，r+1 就是 100001
// 数组开到 100005 是够的；但如果手滑开成 int diff[100000]，
// 当 r == 99999 时 diff[100000] 就越界了📝 凡是差分题，数组大小至少开到
n + 2，图省事可以直接开到
n + 10。
错误 2：忘了 preSum[0] 这一项
int preSum[100005]; // 忘了初始化，preSum[0] 是垃圾值！
for (int i = 1; i <= n; i++) preSum[i] = preSum[i-1] + a[i];
// preSum[0] 不是 0，后面所有区间和全部算错全局数组默认初始化为 0（这点和局部数组不同），所以只要
preSum 是全局数组通常没事；但如果 preSum
声明在 main 函数里（局部数组），必须手动写
int preSum[100005] = {0};，不然
preSum[0] 是垃圾值。
错误 3：铺设道路只累加所有差分绝对值，而不是只累加正数
long long ans = 0;
for (int i = 1; i <= n; i++) {
int diff = d[i] - d[i-1];
ans += abs(diff); // ← 错误！把负的差分也累加了
}负的差分表示"这里在往下降"，不需要额外操作——正的差分才代表"需要新起一次操作去填的量"。把负数也累加进去，答案会偏大。
⭐ 基础题 1：区间和裸题（文件名 t1.cpp，freopen
range1.in/range1.out）
给定 n 个整数，一次查询 [l, r] 的区间和。
输入样例：
5
1 2 3 4 5
2 4
输出样例：
9#include <bits/stdc++.h>
using namespace std;
int a[100005], preSum[100005];
int main() {
freopen("range1.in", "r", stdin);
freopen("range1.out", "w", stdout);
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) preSum[i] = preSum[i - 1] + a[i];
int l, r;
cin >> l >> r;
cout << preSum[r] - preSum[l - 1] << endl;
return 0;
}⭐⭐ 实战题 2：差分裸题（文件名 t2.cpp，freopen
diff1.in/diff1.out）
给定 n 个 0，做 m 次操作，每次给区间 [l, r] 整体加
v，输出最终数组。
输入样例：
5 2
1 3 2
2 4 3
输出样例：
2 5 5 3 0#include <bits/stdc++.h>
using namespace std;
int diff[100005];
int main() {
freopen("diff1.in", "r", stdin);
freopen("diff1.out", "w", stdout);
int n, m;
cin >> n >> m;
while (m--) {
int l, r, v;
cin >> l >> r >> v;
diff[l] += v;
diff[r + 1] -= v;
}
int a[100005] = {0};
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + diff[i];
cout << a[i] << " ";
}
cout << endl;
return 0;
}⭐⭐⭐ 冲刺题 3：请假条统计（文件名
t3.cpp，freopen
leave.in/leave.out）
一个班共 n 天的课程（天数编号 1~n）。有 m 张请假条，每张写着"从第
l 天请假到第 r
天"。求哪一天请假人数最多，最多有多少人（如果并列最多，输出天数最小的那一天）。
提示：这就是"区间加 1"的差分模型——每张请假条对 [l, r]
整体
+1，最后对差分数组求前缀和，得到每天的请假人数，再打擂台找最大值和对应天数。
输入样例：
5 3
1 3
2 5
2 2
输出样例：
2 3（第 2 天被三张请假条都覆盖，人数最多，是 3 人。）
#include <bits/stdc++.h>
using namespace std;
int diff[100005], cnt[100005];
int main() {
freopen("leave.in", "r", stdin);
freopen("leave.out", "w", stdout);
int n, m;
cin >> n >> m;
while (m--) {
int l, r;
cin >> l >> r;
diff[l]++;
diff[r + 1]--;
}
int bestDay = 1, bestCnt = 0;
for (int i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + diff[i]; // 差分求前缀和，还原出每天的人数
if (cnt[i] > bestCnt) { // 打擂台找最大值（并列取天数小的，所以用严格 >）
bestCnt = cnt[i];
bestDay = i;
}
}
cout << bestDay << " " << bestCnt << endl;
return 0;
}这题把差分（区间加）和打擂台（找最大值）拼在了一起——差分负责"快速统计每天覆盖了几张假条"，打擂台负责"从这些天数里挑出人数最多的一天"。
| 工具 | 预处理 | 单次操作 | 用途 |
|---|---|---|---|
前缀和 preSum[i] = preSum[i-1] + a[i] |
O(n) | 查询区间和 O(1)：preSum[r] - preSum[l-1] |
区间求和多次查询 |
差分 diff[i] = a[i] - a[i-1] |
O(n) | 区间加 O(1)：diff[l] += v; diff[r+1] -= v; |
区间批量修改，最后再求前缀和还原 |
两道真题一句话：
preSum[i] - 目前最小的 preSum，打擂台求最大易错点： diff
数组要多开一位（n+2）；局部数组不会自动清零，要写
= {0}。