前缀和与差分是一对互逆的预处理技巧，几乎是所有数组题的底层工具。CSP-J 2025 报告里把它们列为入门级必备 —— 这一节把两者放在一起讲，因为理解它们的关系比单独学更深刻。
前缀和：查询区间和
给定数组
a，多次询问”区间[l, r]的和是多少”
朴素做法每次累加是 O(n) 每次。预处理一个前缀和数组：
prefix[i+1] = a[0] + a[1] + ... + a[i]，约定prefix[0] = 0
之后任意区间和都能 O(1) 算出：
sum(l, r) = prefix[r+1] − prefix[l]
直觉：prefix[r+1] 是前 r+1 个数的和，prefix[l] 是前 l 个数的和，相减就只剩下中间这段。
差分：区间加法
给定数组
a，多次”区间[l, r]整体加k”，最后一次输出结果
朴素做法每次更新是 O(n) 每次。差分数组：
diff[0] = a[0]，diff[i] = a[i] − a[i-1]
差分数组的前缀和就是原数组。区间加法变成两个端点的单点修改：
给
[l, r]加k⇒diff[l] += k，diff[r+1] −= k
为什么？想象 diff 的前缀和过程：从 l 开始的前缀里多了 k，到 r+1 时多出来的 k 又被减掉，正好抵消掉 r+1 之后的影响。
最后做一次扫描重建数组：a[i] = a[i-1] + diff[i]。
一句话总结
| 技巧 | 预处理 | 查询/修改 | 还原 |
|---|---|---|---|
| 前缀和 | O(n) | 区间求和 O(1) | — |
| 差分 | O(n) | 区间加法 O(1) | O(n) 一次性 |
它们都是用一次 O(n) 预处理 / 还原换 多次 O(1) 操作。如果操作数远大于 n，效率提升巨大。
复杂度
- 时间：预处理 O(n)；每次查询 / 区间加法 O(1)
- 空间：O(n) 额外辅助数组
在动画里看什么
- 阶段 1 构建前缀和：prefix[i+1] 一格一格从左到右累加
- 阶段 2 区间查询：高亮区间 [l, r]，下方 prefix[l] 和 prefix[r+1] 同时变红，差就是答案
- 阶段 3 构建差分：每格差分等于相邻原数的差
- 阶段 4 区间加法：只改动两个端点 diff[l] 和 diff[r+1]，不动中间
- 阶段 5 重建：再做一次前缀和即可恢复成更新后的原数组