专题5 · 前缀和与差分
前缀和与差分是一对互逆的数组工具：
前缀和把「区间求和」压成 O(1)，差分把「区间加减」压成 O(1)。
本讲拆开它们的定义、互逆关系，并用两道经典真题练手。
从 O(n²) 到 O(1)：一个问题逼出的优化
有一列数，要反复问「第 l 个到第 r 个加起来是多少」——最直接的写法会超时。
🐢 暴力：每次从头加
int sum=0; for(int i=l;i<=r;i++) sum+=a[i];
单次 O(n)。问 m 次就是 O(n·m)，n=m=10⁵ 时就是 10¹⁰，必炸。
🚀 前缀和：预处理一次
s[i]=s[i-1]+a[i]; // 预处理 O(n) ans = s[r]-s[l-1]; // 每次 O(1)
总复杂度 O(n+m)。多花的只是 s 这一个数组的空间。
前缀和：s[i] 是前 i 项的和
📐 两条等价写法
递推式：s[i] = s[i-1] + a[i]，s[0]=0。
定义式：s[i] = a[1]+a[2]+…+a[i]。
区间和：sum(l,r) = s[r] - s[l-1]。
🧠 为什么减的是 l-1
s[r] 含 a[1]…a[r]；s[l-1] 含 a[1]…a[l-1]。
相减后正好剩下 a[l]…a[r]。
这一步是最经典的「多退少补」：多算的部分减掉，而不是重新数一遍。
🖼️ 看图：为什么是 s[r] − s[l−1]（“多退少补”）
s[0]=0。这样 l=1 时 s[l-1]=s[0] 天然合法，不用为 l=1 写特判——这是 0-based 写法最容易越界的地方。s[l] 这种经典笔误。差分：b[i] 记录「比前一个多多少」
📐 定义式
b[i] = a[i] - a[i-1]（规定 a[0]=0，故 b[1]=a[1]）。
差分数组求前缀和 = 原数组：
b[1]+…+b[i] = a[i]。
🔁 核心操作（背下来）
要把 a 的 [l, r] 全部加 x：
b[l] += x; b[r+1] -= x;
之后对 b 求前缀和，得到的就是修改后的 a。
b[l]+=x 让前缀和从 l 起永久抬升 x；b[r+1]-=x 再从 r+1 起把它抵消回去。中间正好是 [l,r] 这一段被抬高——这就是「区间修改 O(1)」的全部秘密。b[r+1]，而 r 最大为 n，所以数组至少开 n+2（再宽一格更保险）。这是差分题 最高频的越界 WA。前缀和 与 差分 的互逆关系
🔄 三句话记住
前缀和擅长
- 多次问「[l,r] 的和/最大值/异或和」
- 数组不修改、查询很频繁
- 例：水桶清单最后那一步「取峰值」
差分擅长
- 多次「[l,r] 全部加/减 x」
- 只在最后统一查询一次
- 例：水桶清单的加桶、增减序列的操作
前缀和 · 区间查询模拟器
差分 · 区间加模拟器
水桶清单：区间加 + 取峰值
N 头牛，第 i 头在 [s_i, t_i] 内占用 b_i 个桶。问同一时刻最多有多少桶被占用。
🔍 建模
把「时刻」当作下标（1…1000）。每头牛的操作就是：给区间 [s_i, t_i] 加上 b_i。
全部加完后，问「每个时刻用了多少桶」的最大值。
⚡ 两种写法对比
暴力：每头牛循环 t-s+1 次，总计 O(N×1000)。N≤100 其实能过，但思路不通用。
差分：每头牛只改 2 个位置 → O(N)；最后扫一遍求前缀和取最大 → O(1000)。
d[t+1] -= b，不是 d[t]。区间是闭区间 [s,t]，t 这一刻仍在占用，要减到 t 的下一个时刻去。写成 d[t] 会让 t 时刻少算一头牛，样例都对但大数据必错。水桶清单 · 代码走读
#include <iostream> #include <algorithm> using namespace std; int d[1105]; // 时刻最大 1000，多开一点 int main(){ int n; cin>>n; for(int i=0;i<n;i++){ int s,t,b; cin>>s>>t>>b; d[s] += b; // 从 s 起抬升 d[t+1] -= b; // 到 t+1 抵消（不是 t！） } int cur=0, ans=0; for(int t=1;t<=1000;t++){ cur += d[t]; // 前缀和还原本时刻用桶数 if(cur>ans) ans=cur; // 顺手取最大 } cout << ans << "\n"; return 0; }
t+1，t 可达 1000）；② 扫描上界取 1000，别写成 n；③ ans 初值设 0 即可（桶数非负），若题目可能出现负数则初值要设成极小值。增减序列：把「操作」翻译成差分
每次给 [l,r] 全加 1 或全减 1，求让全数列相等的最少操作数与结果种数。
🔑 第一步：翻译操作
「[l,r] +1」在差分上就是 d[l]+=1; d[r+1]-=1;。
「全部相等」⇔ d[2..n] 全为 0。
🎯 第二步：配对消元
设 P = d₂…dₙ 中正数之和，Q = 负数绝对值之和。
- 一个 +1 和一个 -1 可配对用一次操作同时消掉。
- 配完剩下的只能单独消。
样例 a=[1,1,2,2]：d₂=0, d₃=1, d₄=0 → P=1, Q=0 → 操作数 1、种数 2。✓
增减序列 · 配对消元模拟器
高频易错辨析
① 求区间 [l,r] 的和，前缀和怎么写？
② 把 a 的 [l,r] 全部加 x，差分数组要改哪两处？
③ 增减序列中 P=5、Q=3，最少操作数与结果种数各是多少？
一道题 100 分是分档给的——不会正解也要先拿保底
复赛一道题的 100 分由十几到二十几个测试点组成， 前面几档专门为「没想出正解的人」准备。四道题各拿 30~40 分， 加起来往往就是一等奖和二等奖的分界。
① 特判档：先别想算法，看数据范围表
题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行，
就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。
② 暴力档：按题意最直白地写一遍
多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。
③ 特殊性质档：题目里那句「若……」
常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。
④ 正解档：思路定了，就赢了八成
考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。
本讲 2 道题，各自的四档怎么走
水桶清单 · BUCKET
第1档 · 2 分钟n == 1 → 直接输出它的 b
第2档 · 8 分钟
开数组，每个区间逐格 +b，最后扫最大值；时间 ≤ 1000 稳过
第3档 · 10 分钟
所有 b == 1 → 退化成「区间覆盖计数」
第4档 · 15 分钟
差分 d[s]+=b, d[t+1]−=b，前缀和还原后取 max
增减序列 · INCDEC
第1档 · 2 分钟n == 1 → 0 次、1 种结果
第2档 · 8 分钟
逐次选区间模拟（左右配对消），n ≤ 1000 稳过
第3档 · 10 分钟
只做第一问（最少次数），先不管方案数
第4档 · 15 分钟
差分数组正数之和 P、负数绝对值之和 Q；次数 = max(P,Q)，方案数 = |P−Q|+1
0–5 分钟 读题 + 圈出数据范围表里最小的那几档 → 5–15 分钟 写完第 1、2 档并先交一次（保住 20~30 分）→ 15–40 分钟 冲第 3、4 档 → 40–50 分钟 造小数据对拍、检查
freopen 与文件名。本讲知识树与自检清单
🌳 知识树
前缀和：定义 s[i]=s[i-1]+a[i] → 区间和 s[r]-s[l-1] → 1-based + s[0]=0。
差分：定义 b[i]=a[i]-a[i-1] → 区间加 b[l]+=x, b[r+1]-=x → 前缀和还原。
流水线：差分改 → 前缀和还原 → 取答案。
✅ 考场 N 步自检
- 下标从 1 开始了吗？
s[0]/b[0]是不是 0？ - 减的是 l-1 吗？抵消的是 r+1 吗？
- 数组开够 n+2 了吗？（
r+1会越界） - 和最大可能到多少？n=10⁵、a_i=10⁹ 时要 long long。
- 最后一步是不是把差分还原成原数组再取答案？