- 前缀和：反复查一段的和 → 一次算好，每次查 O(1)
- 差分：反复改一段（整段加同一个数）→ 每次改 O(1)，最后一次性还原
它们的关系是：对差分数组求前缀和，就得回原数组。 一个正着用，一个反着用，学会一个就等于学会了两个。
代码加起来不到十行，但它们会出现在后面几乎每一道区间题里 —— 包括第 39 章的线段树，那玩意儿要解决的正是「既要反复查、又要反复改」的场景。
前半场 · 前缀和
1 一句话问题
给一个长度 n 的数组，然后有 q 次询问，每次问你 a[l] + a[l+1] + ... + a[r] 是多少。
输入 8 3 n=8 个数，q=3 次询问
3 -1 4 1 -5 9 2 6
2 5 问 a[2]+a[3]+a[4]+a[5]
1 8 问整个数组的和
4 4 问 a[4] 一个数
输出 -1
19
1从这一章起，数组一律用 a[1] 到 a[n]，a[0] 空着不用。
不是为了好看 —— 是因为前缀和的公式在 1 基下会变得特别干净，
而 0 基会逼着你到处写 +1 -1，然后错一个就全错。
竞赛里的区间题几乎都是 1 基，习惯它。
2 先用纸笔手算一遍
拿上面那组数据，手算 [2,5]：-1 + 4 + 1 + (-5) = -1。
再算 [1,5]：3 + (-1) + 4 + 1 + (-5) = 2。
再算 [1,1]：3。
现在注意一件事：算 [1,5] 的时候，你其实顺带把 [1,1]、[1,2]、[1,3]、[1,4] 都算过了 ——
它们是累加过程中一路经过的中间结果，只是你没记下来。
这就是这一章的全部灵感。先记着这个感觉，第 6 步会用到。
3 暴力：每次都从头加一遍
点「运行 ▶」看结果
逐字翻译，完全正确。n、q 小的时候一点毛病都没有。
4 实测：它有多慢
本机实测（询问次数 = 数组长度，每次询问的区间跨度是半个数组）：
| n = q | 每次现加 O(n·q) | 前缀和 O(n+q) |
|---|---|---|
| 20 000 | 0.07 秒 | 0.003 秒 |
| 50 000 | 0.44 秒 | 0.01 秒 |
| 100 000 | 1.74 秒 | 0.02 秒 |
| 200 000 | 7.01 秒 | 0.03 秒 |
n = q = 10⁵ 是 CSP-J 的常见数据范围，暴力就已经要 1.7 秒了 ——
而大多数题目的时限是 1 秒。这不是「慢一点」，这是 0 分和 100 分的区别。
5 慢在哪：同一段被反复加了无数遍
看这两次询问：
问 [1, 5000] 加了 5000 次
问 [1, 5001] 又加了 5001 次第二次询问里，前 5000 项的和刚刚才算过，但暴力又从头加了一遍。
q 次询问，每次都从头开始，同一批加法被重复了无数遍 ——
这个「重复计算」的味道，是不是和第 2 章的斐波那契很像？
6 ★ 关键的一步
把「从头到 i」的和全部提前算好，存起来。
定义 s[i] = a[1] + a[2] + ... + a[i]，也就是「前 i 个数的和」。特别地 s[0] = 0。
它可以一遍循环全部算出来，每一项只要一次加法：
s[i] = s[i-1] + a[i]; // 前 i 个 = 前 i-1 个 + 第 i 个有了它，任何一段的和都是一次减法：
s[r] = a[1] + ... + a[l-1] + a[l] + ... + a[r]
s[l-1] = a[1] + ... + a[l-1]
------------------------------------------------ 相减
a[l] + ... + a[r] ← 正好是要的答案 = s[r] - s[l-1]。
预处理 O(n)，每次查询 O(1)。总共 O(n + q)。
写成 s[r] - s[l] 会少算 a[l] 那一项 —— 前缀和的头号错误。
记不住就现推：s[l] 里已经包含了 a[l]，减掉它就把要的东西减没了。
所以要减的是「l 前面那一格」，也就是 s[l-1]。
顺便：这就是 s[0] = 0 存在的理由。
当 l = 1 时，s[l-1] 就是 s[0]。如果没有这一格，你就得写个 if (l == 1) 特判；
有了它，公式一视同仁，一个特判都不用。
用一个「零元素」消灭掉一堆边界特判 —— 这是很值得学的一招， 后面的差分、树状数组、线段树都在用。
7 正解
点「运行 ▶」看结果
点「运行 ▶」看结果
8 单步看它长出来
先看「前缀和」这一栏：
- 预处理阶段：
s一格一格往右长，每一格只做一次加法。 - 查询阶段：绿色的
s[r]减掉红色的s[l-1]，中间蓝色那段就是要的答案。 - 把询问改成
1 8，看红色那一格落在s[0]上 —— 那一格是 0，所以什么都没减掉。 这就是「零元素消灭特判」的现场。
（「差分」那一栏先别急，第 11 步再回来看。）
9 ★ 对拍验证
把「前缀和」那一栏换成你自己默写的，再点开始。
值得故意写错的：
s[r] - s[l]（少减一格）→ 每次都少算a[l]s[i] = s[i-1] + a[i-1]（下标抄错）→ 整体错位s数组只开 n 不开 n+1 →s[n]越界s用int（数据大时会溢出）→ 这个对拍不一定抓得住！ 因为生成器造的数据小。真实比赛里10⁵个10⁹就爆int了。 前缀和一律开long long，这是习惯问题，不是判断问题。
后半场 · 差分
10 反过来的问题
现在把题目反过来：不查了，改成改。
给一个数组，q 次操作，每次把 a[l..r] 里的每个数都加上 v。
所有操作做完之后，输出整个数组。
输入 8 3
3 -1 4 1 -5 9 2 6
2 5 3 a[2..5] 每个加 3
1 8 -2 整个数组每个减 2
6 8 10 a[6..8] 每个加 10
输出 1 0 5 2 -4 17 10 14暴力当然还是逐字翻译（O(n·q)）：
点「运行 ▶」看结果
11 ★ 关键的一步：只记变化量
定义 d[i] = a[i] - a[i-1]（相邻两项的差，约定 a[0] = 0）。
现在把 a[l..r] 整体加 v。想一想哪些「相邻两项的差」变了：
下标: l-1 l l+1 ... r r+1
原数组: 8 2 5 ... 7 4
每个加 3: 8 5 8 ... 10 4
↑ ↑
这里的差变大了 3 这里的差变小了 3
中间那些差 一 点 没 变区间内部每一项都加了同一个 v，相邻两项的差当然不变。
真正变了的只有两处边界：
d[l] += v; // l 和 l-1 之间的差，大了 v
d[r+1] -= v; // r+1 和 r 之间的差，小了 v不管区间多长，一次操作只改两个数，O(1)。
全部操作做完之后，对 d 求一遍前缀和，就还原出最终的数组：
a[i] = d[1] + d[2] + ... + d[i]为什么？因为 d[1]+...+d[i] = (a[1]-a[0]) + (a[2]-a[1]) + ... + (a[i]-a[i-1])，
中间全部消掉，只剩 a[i] - a[0] = a[i]。这叫望远镜求和，
式子写出来一眼就能看见它们互相抵消。
差分和前缀和是一对逆运算。 这就是为什么这两个东西要放在同一章里讲。
r 可以等于 n，那 d[r+1] 就是 d[n+1] —— 它在原数组外面。
这一格必须留出来（虽然还原时用不到它），否则就是数组越界。 运气好当场崩溃，运气不好静默地改坏了别的变量，然后你查一晚上。
这是差分的头号翻车点，比公式本身更容易出事。
点「运行 ▶」看结果
点「运行 ▶」看结果
现在回到上面那个动画，切到**「差分（改区间）」**那一栏再看一遍：
- 每次区间加，只有两格变蓝。中间那些格子从头到尾没被碰过。
- 最后「还原」那一段，用的就是前缀和那个循环，一个字都没改。
12 ★ 对拍验证
把「差分」那一栏换成你自己默写的，再点开始。
值得故意写错的：
d[r] -= v（少了 +1）→ 区间末尾那一项少加了vd[r+1] += v（符号写反）→ 后面所有数全错- 数组只开
n+1，遇到r = n→ 越界 - 忘了先用原数组建
d（直接从全 0 的d开始）→ 原数组的值全丢了
再进一步
13 二维前缀和：矩形里的和
同样的思路搬到二维：给一个矩阵，反复问某个子矩形里所有数的和。
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];
// ↑上面那块 ↑左边那块 ↑左上角那块被算了两遍，减掉一次查询 (x1,y1) 到 (x2,y2)：
s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]
// 大矩形 砍掉上面 砍掉左边 左上角被砍了两次，补回来两个式子是同一个道理。不要背 —— 在纸上画一个 4×4 的格子， 把「上面那块」「左边那块」「左上角那块」涂成三种颜色， 你会看到左上角被涂了两次。画一次，一辈子不用再背。
点「运行 ▶」看结果
给一个子矩形整体加 v，在二维差分数组上要动四个角：
d[x1][y1] += v;
d[x1][y2+1] -= v;
d[x2+1][y1] -= v;
d[x2+1][y2+1] += v;然后对 d 求一次二维前缀和还原。原理和一维完全一致，只是边界从 2 个变成 4 个。
这一章不展开（CSP-J 考到二维差分的概率不高），但你现在已经有能力自己推了 ——
推完拿上面那个二维对拍器验一验，把 brute2d 改成「区间加」版本就行。
14 什么时候用不了
前缀和的前提是预处理之后数组不再改动。
一旦中间有人改了 a[5]，那么 s[5] 到 s[n] 全部作废，重算要 O(n)。
如果题目是「改一次、查一次、改一次、查一次……」交替进行，前缀和就没有优势了。
又要反复改、又要反复查 —— 这正是第 38 章树状数组、第 39 章线段树要解决的问题。 到那时你会发现，它们干的事情本质上就是「可以修改的前缀和」。
所以这一章不只是一个技巧，它是后面那两章的引子。判断标准很简单：
| 场景 | 用什么 |
|---|---|
| 只查不改 | 前缀和 O(1) 查 |
| 只改不查（最后才输出） | 差分 O(1) 改 |
| 又改又查 | 树状数组 / 线段树（第 38、39 章） |
15 自测
- 洛谷 P8218 求区间和 —— 一维前缀和模板题，五分钟应该写完
- 洛谷 P1719 最大加权矩形 —— 二维前缀和 + 枚举矩形。经典组合，值得写熟
- 洛谷 P2367 语文成绩 —— 差分模板题。不用差分会 TLE，正好验证这一章学没学会
- 洛谷 P3406 海底高铁 —— 差分的实战应用，要先想清楚「哪一段被走了几次」
第 7 章双指针与滑动窗口，思路上和这一章是亲戚： 都是利用「上一步的结果」，避免从头再来一遍。
区别在于前缀和是「提前全算好」，而双指针是「顺着往前挪，边挪边改」。