先问个问题：你刷题的时候，是不是经常遇到一类题——给一个数组，让你反复求某个区间的和，或者反复给某个区间加上一个数？我第一次碰到这种题，上来就写个for循环硬算，数据量小还能应付，一旦数组长度到十万、操作次数到十万，直接超时超到怀疑人生。

后来我才明白，这类题根本不需要“每次现算”，而是可以提前把答案“存起来”，或者把修改动作“记下来”，最后一次性算总账。这套思想就是今天要聊的前缀和和差分法。

很多人把这两个东西当两个独立的模板背，背完就忘，遇到变形题还是不会。但只要你把它们的本质理清楚，会发现它们根本就是同一件事的两面——一个负责提前算好答案，一个负责提前记下修改，两者互为逆运算。

这篇文章我会从最朴素的暴力做法讲起，一步一步推导出前缀和和差分的核心公式，再用真实题目场景带你识别“什么时候该用哪个”，最后把我踩过的坑、调试心得全部倒出来。读完你不仅能默写模板，还能真的理解为什么这么写、什么时候不该用。

1. 前缀和：预处理换查询速度的“离线账本”

1.1 从一个最朴素的需求说起

想象你有个长度为n的数组a，里面存着某个城市每一天的用电量。现在领导心血来潮，一口气问了你一万个问题，每个问题都是“第l天到第r天总共用了多少电”。

最直觉的做法是：来一个问题，就循环累加一次。

int sum = 0; for (int i = l; i <= r; i++) { sum += a[i]; }

这样做一次查询的时间是O(n)，一万个查询就是O(n * m)。如果n和m都是10^5，恭喜你，你的程序可以稳稳跑上几十秒，评测系统直接给你一个红色的 Time Limit Exceeded。

问题出在哪里？出在每次查询都在重复计算相同的东西。第 1 天到第 100 天的和，和第 1 天到第 50 天的和，明明可以互相借用，但暴力循环完全没利用这个关系。

1.2 账本思维：把每一段的累计值先记下来

这时候就该引入前缀和了。定义：

s[i] = a[1] + a[2] + ... + a[i]

也就是说，s[i]表示从开头到第i个位置这一段的总和。它像一本账本，每一行记录了“从第一天到今天一共用了多少电”。

构建这本账本极其简单，一个循环就搞定：

for (int i = 1; i <= n; i++) { s[i] = s[i - 1] + a[i]; }

s[i - 1]是前一天的累计，加上今天的a[i]，就是今天的累计。时间复杂度O(n)，空间复杂度O(n)。

有了这本账本之后，你要查“第l天到第r天的用电量”，公式就变成了：

sum(l, r) = s[r] - s[l - 1]

为什么？因为s[r]是从头加到r的总和，s[l - 1]是从头加到l - 1的总和，两者一减，剩下的正好是l到r这一段。时间复杂度直接降到O(1)。

一万个查询，一个O(n)的预计算加一万个O(1)的查询，跑起来几乎瞬间完成。

1.3 这里的核心思想值得单独拎出来说

前缀和的关键不是那个公式，而是空间换时间和离线预处理这两个思想。

所谓离线预处理，就是你先把所有可能用到的“累计值”全部算好放在那里，等查询真正到来时，你只需要做一次减法。这和现实生活中记账很像——你不会等到年底才去翻整年的账本算总账，而是每天都把累计值记一笔，年底直接读最后一行就行。

我在实际做题过程中发现，很多人会把前缀和跟“动态维护”搞混。如果你需要一边修改数组元素、一边查询区间和，前缀和是不能直接用的，因为修改一个元素会导致后面的所有s[i]全部失效，你需要重新构建整本账本，复杂度又退化成了O(n)。这种情况应该去学线段树或者树状数组，那是另一个话题了。

使用前缀和有一个前提：你的查询必须是“只读”的——整个数组在查询期间不能有任何修改。如果既有修改又有查询，就要考虑差分、树状数组这类工具了。

1.4 一维前缀和的代码模板

为了方便你直接抄作业，我贴一份 C++ 和一份 Python 的实现。

#include <bits/stdc++.h> using namespace std; const int N = 100005; long long a[N], s[N]; int main() { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; s[i] = s[i - 1] + a[i]; // 边读入边构建前缀和 } while (m--) { int l, r; cin >> l >> r; cout << s[r] - s[l - 1] << endl; } return 0; }

n, m = map(int, input().split()) a = list(map(int, input().split())) # 注意 Python 的索引从 0 开始，这里构建前缀和时前面垫一个 0 s = [0] * (n + 1) for i in range(n): s[i + 1] = s[i] + a[i] for _ in range(m): l, r = map(int, input().split()) print(s[r] - s[l - 1])

这里有个小细节：C++ 数组下标从 1 开始，让s[0] = 0，这样查询l = 1时s[0]刚好是 0，不需要额外特判。Python 则通过前面垫一个 0 的方式，把下标语义转换成了同样的模型。这个“哨兵位”技巧看似不起眼，却能省掉一堆边界判断，后面二维前缀和里它更重要。

2. 二维前缀和：容斥原理的工程化用法

一维前缀和解决的是“一条线”上的区间求和问题。但实际场景不可能永远是一条线——比如给你一块停车场，每个车位停了几辆车，你要反复问“从第x1行第y1列到第x2行第y2列这个矩形区域里总共停了多少辆车”，这种二维矩阵的区间求和问题，就得升级到二维前缀和。

2.1 二维前缀和的构建公式

二维前缀和的定义是：

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]

很多第一次接触的人看到这个公式就蒙了，为什么要加一个减一个？

你想象一个矩形被分成四块——左上角的S[i-1][j-1]、右上边的那一条、左下边的那一条、以及右下角当前位置。S[i-1][j]已经包含了左上角和左下边，S[i][j-1]已经包含了左上角和右上边。把这两个加起来，左上角那块被加了两次，所以要减去一次S[i-1][j-1]，最后再加上当前格子的值a[i][j]。

这就是著名的容斥原理——计算重叠区域时，先加进来，再把多加的减掉。这个思想在二维前缀和里用得非常纯粹。

2.2 子矩形求和的查询公式

构建好S之后，查询任意矩形(x1, y1)到(x2, y2)的和，公式变成：

sum = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

你看，又是容斥原理：大的矩形减去上边一条、左边一条，但左上角那块被减了两次，所以再加回来一次。

我在早期学这个公式的时候，总是搞混到底哪个减哪个加。后来我自己想了一个笨办法：画一个 3×3 的网格，用行号和列号标好每一个位置，自己手写一遍公式，把每个格子被加了几次、被减了几次全部标出来。试一次就再也忘不了。

2.3 二维前缀和的完整代码

这里给出一个从 1 开始索引的二维前缀和模板，n行m列：

#include <bits/stdc++.h> using namespace std; const int N = 1005; long long a[N][N], S[N][N]; int main() { int n, m, q; 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; long long ans = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]; cout << ans << endl; } return 0; }

2.4 最容易翻车的细节：偏移量

二维前缀和最常翻车的地方不是公式背不出来，而是数组索引的偏移。

如果你用 C++ 且下标从 0 开始，那么构建时S[i][j]的定义要相应变化，查询时也要把(x1, y1)看成矩形左上角元素本身的位置，一不小心就会整体错位一格，结果全部出错。我的经验是：能采用 1-based 就采用 1-based，把第 0 行第 0 列全部留成 0，这样S[0][j]和S[i][0]都是天然的 0，就不需要再去特判“第一行没有上一行”这种边界了。

如果你用的是 Python，需要在二维列表外面包一圈 0，具体做法是把S初始化为(n+1) × (m+1)的全 0 矩阵，然后内层循环从 1 到 n、1 到 m 逐个填。

3. 差分：区间修改的“反向账本”

前缀和解决的是“很多次查询、少量修改”的场景。但现实里还有另一类完全镜像的问题——很多次区间修改、最后只需要查一次最终结果。

比如你运营一个小区停车系统，车主们会频繁地预约某一段时间内的停车位，你需要在系统里记录：某一整段日期区间内的车位占用数全部加 1。预约来了几万条，最后你只需要知道每一天到底被预约了多少次。如果你每次预约都去把区间里的每个数加一遍，碰到一个超大区间加几万次预约，复杂度又是爆炸。

这时候，差分法登场。

3.1 差分数组的定义

差分数组diff的定义是这样的：

diff[i] = a[i] - a[i - 1]

也就是说，差分数组里存的是原数组每个位置和它前一个位置的差值。特别地，diff[1] = a[1]。

这里有个非常妙的性质：原数组a恰好是差分数组diff的前缀和。

怎么理解？你从diff[1]开始累加：

a[1] = diff[1]

a[2] = diff[1] + diff[2]

a[3] = diff[1] + diff[2] + diff[3]

发现没有？a[i]等于diff数组前i项的和。也就是说，对一个差分数组做前缀和，就能还原出原数组。差分跟前缀和天生就是一对互逆操作——前缀和是“累加”，差分是“求差”。

3.2 区间加操作的 O(1) 实现

差分的思想等价于“记录变化量”。

还是停车系统那个例子，如果我要把区间[l, r]上的所有数全部加c，我根本不用去动区间里每一个元素，我只需要在差分数组上做两个小动作：

diff[l] += c

diff[r + 1] -= c

就完了。复杂度O(1)，跟区间长度完全无关。

为什么这么做是对的？因为差分数组记录的是“变化率”。在l这个位置加c，意味着从l开始，原数组的值全都比之前多了c；到了r + 1再减掉c，意味着从r + 1开始又恢复正常。中间那段自然就保持了“多了c”的状态。

想象你在一段路上洒水：diff[l] += c是在l这个位置打开了水龙头，diff[r+1] -= c是在r+1的位置关掉了水龙头。水只覆盖了[l, r]这一段。

等到所有修改都做完，你只需要对差分数组做一遍前缀和，就能得到每一个位置的最终值：

for (int i = 1; i <= n; i++) { diff[i] += diff[i - 1]; }

此时diff[i]就是最终的a[i]。

3.3 差分的构建方式和完整代码

构建差分数组有两种方式，我个人更推荐第二种。

第一种：先有原数组a，然后直接diff[i] = a[i] - a[i-1]。

第二种：一开始全 0，直接通过区间更新操作来构建。比如已知初始时数组全是 0，现在要执行m个区间加操作，你直接对diff数组做diff[l] += c和diff[r+1] -= c，等操作全部做完，对diff做前缀和还原，就得到了最终数组。

#include <bits/stdc++.h> using namespace std; const int N = 100005; long long diff[N]; int main() { int n, m; cin >> n >> m; while (m--) { int l, r, c; cin >> l >> r >> c; diff[l] += c; diff[r + 1] -= c; } for (int i = 1; i <= n; i++) { diff[i] += diff[i - 1]; cout << diff[i] << " \n"[i == n]; } return 0; }

Python 版本类似，用长度为n + 2的列表（多一位是为了防止r + 1越界访问）：

n, m = map(int, input().split()) diff = [0] * (n + 2) for _ in range(m): l, r, c = map(int, input().split()) diff[l] += c diff[r + 1] -= c cur = 0 for i in range(1, n + 1): cur += diff[i] print(cur, end=' ') print()

3.4 差分适用的场景边界

差分看起来美，但它有一个明显限制：只能做“最后统一查结果”这一类离线操作。如果你在修改过程中需要随时查询某个位置的当前值，那差分就帮不上忙了——因为你没有还原最终数组，中间时刻的值是算不出来的。

另外，差分只能处理区间加（或减）同一个数的操作。如果某个操作是“把区间[l, r]里所有数都变成某个值”，差分也无法直接处理，那要用线段树的区间赋值功能。这一点在面试和笔试里经常被拿来出变体题，要特别注意审题。

4. 前缀和与差分互为逆运算：一个思想的两张面孔

很多人学完上面两节，仍然觉得前缀和和差分是两个独立的知识点。但如果你能把它们放在一起看，会发现整个思路瞬间清晰了。

4.1 互逆关系的数学表达

前缀和：s[i] = a[1] + a[2] + ... + a[i]

差分：d[i] = a[i] - a[i - 1]

如果先对数组a求差分，得到d，再对d求前缀和，你能得到什么？得到的还是a。

如果先对数组a求前缀和，得到s，再对s做差分，你得到什么？也还是a。

也就是说，差分操作是前缀和操作的逆运算，两者互为“撤销”关系。这个性质看起来简单，但应用价值极高。

4.2 联合使用的经典场景：区间加 + 区间求和

假设你要面对的问题是：先执行m次区间加操作（每次给[l, r]加上c），然后再执行k次区间求和查询（查[l, r]的总和）。如果暴力做，每次操作或查询都是O(n)，总复杂度O((m + k) * n)，大概率超时。

正确做法是把两个工具串起来：

1. 用差分数组diff记录所有的区间加操作，复杂度O(m)。
2. 对差分数组做前缀和，还原出最终的a数组，复杂度O(n)。
3. 再对a建立前缀和数组s，复杂度O(n)。
4. 之后每个查询sum(l, r)就是O(1)。

总复杂度从O((m + k) * n)降到了O(m + n + k)。这是一个数量级级别的提升，数据规模一大，两者就是“超时”和“秒过”的区别。

4.3 嵌套使用的进阶思路

更有意思的是，你会发现差分和前缀和的嵌套可以玩出花来。我记得遇到过一个模拟题：要求对一个数组执行若干次“区间加上一个等差数列”——也就是每个位置的加值不是常数，而是随着下标线性变化。

当时我花了好一会儿才想到：这种操作不能直接用普通的差分，但可以用两次差分。因为等差数列的差分是一个常数，而常数的区间加又可以用差分实现。于是先对“变化率”做差分，再对差分做差分，最后再对二阶差分做两次前缀和还原原数组。整个过程其实就是反复利用“差分是前缀和的逆运算”这个性质。

这类嵌套题目不强求所有人都能一眼看穿，但理解互逆关系之后，至少你再遇到类似变形题，会有个大概的推导方向，而不是完全无从下手。

5. 实战套路识别：拿到一道题，怎么快速判断该用哪个

学了公式，背了模板，最后拦在很多人面前的问题是：**拿到一道新题，怎么知道它该用前缀和还是差分？**我按照自己的做题经验，整理了一套判断流程，希望对你也有用。

5.1 问题特征对照表

这张表不是绝对的，但覆盖了大多数常规场景。判断的核心只有一个问题：你的操作是“查询”还是“修改”？是发生在“事前”还是“事后”？

5.2 四个拿来即用的模拟案例

案例 1：图书馆借阅记录

有三个读者，分别借了第 1 天到第 5 天、第 3 天到第 8 天、第 5 天到第 10 天的书。你要回答每个读者借书区间内的总借阅天数。

这个场景是“区间求和”，直接用前缀和，先把每一天是否有人借书的计数数组构建出来，再做前缀和，每个查询一次相减搞定。

案例 2：车库预约系统

一万个车主，每人预约一个时间段[l, r]，最后你要知道每个时刻被多少个预约覆盖。这是典型的“多次区间加、最后统一查结果”，差分数组一把梭。

案例 3：公交站客流统计

公交车一圈下来，每个站有人上车有人下车，已知每个站的上下车人数，要求计算每一段路程上的最大客流。这个本质是“区间加（上车在起点、下车在终点）”，也是差分。

案例 4：展厅展品摆放

一个二维展厅，多个展商各自申请一个矩形区域作为展位，最后要输出每个格子被多少个展位覆盖。这是二维差分的直接应用。

5.3 最容易混淆的边界情况

有一种题经常让人纠结：它给了你一个数组的“操作序列”，每个操作是“把第l到第r个元素都加c”，然后问你某个前缀的最终和。

这种题很多人第一反应是前缀和，但仔细看，这里有修改操作，不是只读查询。正确理解是：先用差分把修改全部记录下来并还原数组，然后再用前缀和去回答最终查询。记住，前缀和管不了修改，差分管不了查询，两者经常要联合作战。

6. 我踩过的坑，和排查这些坑的完整思路

写到这里，公式、模板、场景都讲完了，再分享一些我实际做题时踩过的坑。这些坑教科书上不会写，但每一道都能让人卡上半天。

6.1 下标从 1 还是从 0：看似小事，错起来要命

我第一次写二维前缀和的时候，偷懒用了 0-based 的下标。结果写查询公式时，(x1 - 1)和(y1 - 1)这两个偏移量怎么调都不对，测试数据一跑，前几个对，后面全错。

后来我老老实实改成 1-based，把第 0 行第 0 列全部填 0，对着公式逐项代入验证，一次性通过。从那以后，我只要看到前缀和、差分这类题，第一件事就是先把下标统一成 1-based，绝不在索引上省事。

排查建议：如果代码跑出来结果整体错位，先用一组非常小、能肉眼验证的数据（比如 3×3 矩阵），手动算一遍期望值，再跟程序输出对比，多半能定位到是偏移量写错了。

6.2 边界上的 r + 1 越界

差分的区间加操作是diff[r + 1] -= c。如果r = n，那r + 1就超出数组范围了。数组开小了的直接后果是：要么运行时报错，要么修改了未知内存导致答案莫名其妙错乱。开数组的时候一定要多开一个位置，比如N = n + 2。

我自己有个习惯：所有和差分打交道的数组，一律开到n + 2或者全局数组N + 5，多出来的几个位置不会影响正确性，但能避免边界问题。

6.3 大数据溢出问题

前缀和数组里存的是“到当前位置的累计和”，数据一多，累加值很容易超出int的范围。比如数组里每个元素是10^9，数组长度是10^5，前缀和就能到10^14，直接爆int。

在 C++ 里，前缀和和差分数组都建议直接用long long，哪怕当前测试数据小，也先保证泄不了。Python 则没有这个问题，但要注意别在 Java 里用int大意了。

6.4 背模板却不理解原理，变一下就蒙

我见过不少同学，把这个模板背得滚瓜烂熟，但换一种问法就卡住。比如题目说“每隔一个位置加一次”，或者“区间内最大值是多少”，前缀和和差分都没法直接套用。

这时要回到思想本身：前缀和解决的是“可叠加的区间总和”，差分解决的是“可叠加的区间整体偏移”。如果这个操作不满足“叠加”性质（比如求最大值、求中位数），就要果断放弃前缀和/差分，考虑其他数据结构，而不是硬套模板。

6.5 二维差分的边界还原

二维差分是差分数组的二维扩展，修改矩形(x1, y1)到(x2, y2)需要在四个位置做标记：

diff[x1][y1] += c; diff[x1][y2 + 1] -= c; diff[x2 + 1][y1] -= c; diff[x2 + 1][y2 + 1] += c;

然后对diff做二维前缀和还原。如果你搞不清楚这四个位置为什么这样标，建议把它跟二维前缀和的容斥公式对照着看——它们本质上是同一套逻辑的镜像操作。此处经常有人漏掉右下角那个加号，导致还原出来的矩阵外围区域受到错误影响，排查起来非常隐蔽。

7. 学习建议：怎么练才能真的掌握这套思想

7.1 小数据手动仿真

每次学一个新算法，我都建议先找一组很小的数据，比如数组长度 5，手动把前缀和数组、差分数组全部列出来，一笔一笔算清楚。这个动作看起来慢，但它能让你对公式的每一步都有直觉感知，远比直接看十道题更有效。

7.2 把模板默写到条件反射

前缀和、差分、二维前缀和、二维差分，这四个模板是算法竞赛和面试题里的“地基工具”，应该练到几乎不需要思考就能写出来的程度。我曾经在纸上一遍一遍默写这几个模板，直到闭着眼睛也能正确写出边界条件。熟练度到了，遇到复杂题才能把精力放在更高层的思路上，而不是被基础细节卡住。

7.3 从题目反推考点

刷题时看到题解用了前缀和或差分，别急着划走，反过来想一想：**这道题如果不告诉我用前缀和，我自己能不能看出来？**下一次遇到类似题，能不能主动联想到？这种“反推”训练对提高题型敏感度特别有用。

坦白讲，我一开始也把前缀和和差分当公式背，直到某天做题时突然意识到“差分数组做前缀和就是原数组”，有种被击穿的感觉——原来这两个东西是配套的。那次顿悟之后，我再看到相关题目，心里就有了底：先分清是查询还是修改，是二维还是一维，是单次还是多次，工具就自己跳出来了。

如果你现在还在为这两块内容头疼，不妨按我上面的方法，挑几道经典题，用笔手写一遍过程，比干看十篇攻略强得多。做题遇到卡壳，欢迎回来翻翻这篇文章——我相信你用得上。