先问个问题你刷题的时候是不是经常遇到一类题——给一个数组让你反复求某个区间的和或者反复给某个区间加上一个数我第一次碰到这种题上来就写个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初始化为(n1) × (m1)的全 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] cdiff[r 1] - c就完了。复杂度O(1)跟区间长度完全无关。为什么这么做是对的因为差分数组记录的是“变化率”。在l这个位置加c意味着从l开始原数组的值全都比之前多了c到了r 1再减掉c意味着从r 1开始又恢复正常。中间那段自然就保持了“多了c”的状态。想象你在一段路上洒水diff[l] c是在l这个位置打开了水龙头diff[r1] - c是在r1的位置关掉了水龙头。水只覆盖了[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[r1] - 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)大概率超时。正确做法是把两个工具串起来用差分数组diff记录所有的区间加操作复杂度O(m)。对差分数组做前缀和还原出最终的a数组复杂度O(n)。再对a建立前缀和数组s复杂度O(n)。之后每个查询sum(l, r)就是O(1)。总复杂度从O((m k) * n)降到了O(m n k)。这是一个数量级级别的提升数据规模一大两者就是“超时”和“秒过”的区别。4.3 嵌套使用的进阶思路更有意思的是你会发现差分和前缀和的嵌套可以玩出花来。我记得遇到过一个模拟题要求对一个数组执行若干次“区间加上一个等差数列”——也就是每个位置的加值不是常数而是随着下标线性变化。当时我花了好一会儿才想到这种操作不能直接用普通的差分但可以用两次差分。因为等差数列的差分是一个常数而常数的区间加又可以用差分实现。于是先对“变化率”做差分再对差分做差分最后再对二阶差分做两次前缀和还原原数组。整个过程其实就是反复利用“差分是前缀和的逆运算”这个性质。这类嵌套题目不强求所有人都能一眼看穿但理解互逆关系之后至少你再遇到类似变形题会有个大概的推导方向而不是完全无从下手。5. 实战套路识别拿到一道题怎么快速判断该用哪个学了公式背了模板最后拦在很多人面前的问题是**拿到一道新题怎么知道它该用前缀和还是差分**我按照自己的做题经验整理了一套判断流程希望对你也有用。5.1 问题特征对照表题目特征推荐工具核心原因多次区间求和数组不修改前缀和预处理后查询 O(1)多次区间加最后只需输出最终数组差分修改 O(1)最后统一还原多次区间加接着多次区间求和差分 前缀和先差分记录修改再前缀和支撑查询二维矩阵多次子矩阵求和二维前缀和容斥原理把查询降到 O(1)二维矩阵多次子矩阵加最后求最终矩阵二维差分二维修改 O(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 从题目反推考点刷题时看到题解用了前缀和或差分别急着划走反过来想一想**这道题如果不告诉我用前缀和我自己能不能看出来**下一次遇到类似题能不能主动联想到这种“反推”训练对提高题型敏感度特别有用。坦白讲我一开始也把前缀和和差分当公式背直到某天做题时突然意识到“差分数组做前缀和就是原数组”有种被击穿的感觉——原来这两个东西是配套的。那次顿悟之后我再看到相关题目心里就有了底先分清是查询还是修改是二维还是一维是单次还是多次工具就自己跳出来了。如果你现在还在为这两块内容头疼不妨按我上面的方法挑几道经典题用笔手写一遍过程比干看十篇攻略强得多。做题遇到卡壳欢迎回来翻翻这篇文章——我相信你用得上。