任何刷到这篇内容的朋友估计多半是被信息学奥赛或者算法题里的“前缀和与差分”逼过来的。说实话它俩算是数据处理里最基础的两个工具基础到教科书只会丢给你几行公式但真到了做题的时候很多人又会开始纠结什么时候该用前缀和什么时候该用差分二维的又该怎么写。我过去带过不少准备信奥的选手也陪人一起死磕过算法题发现大家卡住的几乎都是同一个问题没搞懂这两个东西实际上是同一套“累加与差量”逻辑的正反两面。有一点先说明这里的差分是算法里的差分数组不是硬件里常说的差分信号、差分放大电路这一类概念看到那类热词点进来的朋友别跑错片场。这篇我直接用竞赛常用的套路加上日常能听懂的类比把这两个工具怎么用、为什么能用、边界上有哪些坑一次性掰开揉碎讲清楚适合刚入门算法的学生也适合临阵磨枪需要补上这一块的选手。1. 一对互为逆运算的兄弟1.1 前缀和解决的是“频繁区间求和”先聊前缀和。它的目标非常单纯给你一个数组你需要在极短的时间内回答任意一个连续区间的和是多少。举个来自生活的例子。你手里有一张班级成绩单上面是每个学生的分数按学号排好。现在老师连续问几十次从第3号到第8号的同学总分是多少最笨的办法是每次把第3号到第8号的分数累加一遍如果班级有1000人每次都要现场加5个数字看着不多但如果每个区间都很长呢假如一次问从第1号到第900号那一次就得加900次问100次就是9万次运算。前缀和的做法是在学习委员登记成绩的时候顺手把“从第1号到第i号的总分”全部算好记作s[i]。以后老师再问第l号到第r号的总分直接用s[r]减去s[l-1]就行。因为“1到r的总分”里已经包含了“1到l-1的总分”多出来的部分正好是“l到r”这一段。这就是前缀和的核心思想预处理一遍把历史信息累计起来让每次查询都变成两次数组访问和一次减法也就是O(1)时间。注意重点是“多次查询”。如果题目只让你求一次区间和暴力没必要优化可一旦查询次数达到几万、几十万O(n)的单次查询就会把整体复杂度拖到O(n·m)这个量级在信奥里基本是必超时的。1.2 差分解决的是“多次区间更新”差分解决的问题刚好是另一面给你一个数组每次操作都是把某个区间[l, r]内的所有元素统一加上一个值v操作完之后再让你输出或查询最终每个位置的值。如果还是上面的成绩单相当于老师说“第3号到第8号同学每人平时分加5分”然后又一句“第5号到第10号每人加3分”来回折腾很多次。暴力做法很容易理解每来一次操作就循环从l到r把每个位置加一遍。假想一下数组长度是10万操作次数是10万每次都改差不多半个数组运算量直奔上千亿程序不超时才怪。这时候差分数组登场我们不直接改原数组而是维护另一个数组d用d来表示变化量。每个区间加的操作在d数组上只需要改两个位置d[l]加上vd[r1]减去v。等所有操作都记完了再把d数组从头累加一遍就能还原出原数组每位的最终值。这个思路本质上是把“区间修改”批量记录下来最后一次性生效复杂度从O(n)每次直接降到O(1)每次。1.3 一正一逆前缀和与差分正好互逆很多人把这两个知识点当成两套独立模板背背完就混。其实它们的关系特别简单差分数组做一遍前缀和就能还原出原数组原数组做一遍差分就能得到差分数组。d[i] a[i] - a[i-1]这是差分a[i] d[1] d[2] ... d[i]这是前缀和。两个操作彼此抵消就像加法和减法、打包和拆包。理解了这一层你会发现许多题目根本不需要纠结“该用哪个”因为它们常常是同一个流程的前半段和后半段。先差分记录变化再前缀和还原结果这是后面章节里组合实战的核心。2. 前缀和怎么用代码细节全在这里2.1 一维前缀和模板与下标技巧先给一个最简单也最实用的C模板我默认下标从1开始存而不是0。这样做的原因后面单独讲竞赛里绝大多数前缀和题都习惯从1开始强烈建议直接入门就养成这个习惯。#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long a(n 1), s(n 1, 0); for (int i 1; i n; i) { cin a[i]; s[i] s[i - 1] a[i]; } while (q--) { int l, r; cin l r; cout s[r] - s[l - 1] \n; } return 0; }这里s[i]表示原数组前i个元素的和。构造时s[i] s[i-1] a[i]每一次都利用上一步的结果用空间换时间。查询[l, r]区间时输出s[r] - s[l-1]即可。我用了vector 而不是int这是个很重要的习惯数组长度一旦超过几万前缀和的值就可能超出int范围比如10万个10万相加结果轻松到10的10次方以上int会溢出变成负数排查起来相当头疼。2.2 二维前缀和的容斥公式二维前缀和是信奥常考的进阶版本它的核心是一个容斥公式。比如你有一张n行m列的矩阵想快速求出任意子矩阵[(x1,y1)到(x2,y2)]的和可以先预处理出一个二维前缀和数组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]是上方矩形区域的和s[i][j-1]是左方矩形区域的和把两个加在一起左上角那块s[i-1][j-1]被加了两次所以要减掉一次最后再加上当前格子a[i][j]。整个过程很像把两块布拼在一起重叠的地方只能算一次。查询子矩阵(x1,y1)到(x2,y2)的和时公式是sum s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]你可以把s[x2][y2]当作整个大矩形减去上方和左方的两块之后左上角重叠减多了的部分要加回来又是同一个容斥思路。我最初学这段时觉得四个角记来记去容易串后来自己想了个土办法凡是“减”的下标里带x1-1或y1-1的最后一定要把两个都减的加回来。#include bits/stdc.h using namespace std; int main() { int n, m, q; cin n m q; vectorvectorlong long s(n 1, vectorlong long(m 1, 0)); for (int i 1; i n; i) { for (int j 1; j m; j) { long long x; cin x; s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] x; } } while (q--) { int x1, y1, x2, y2; cin x1 y1 x2 y2; long long res s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]; cout res \n; } return 0; }核心变化就是把一维的“两个下标相减”扩展成二维的“四个角容斥”。只要预处理成了任何子矩阵查询都是O(1)这在处理图像、地图、棋盘类问题时特别有用。2.3 前缀和不只是用来求和的实际做题时前缀和的用法远不止“区间求和”这一个。很多经典题的本质是“利用前缀和把问题转化成两个值之间的比较”。举个例子最大子段和问题给定一个数组找出一段连续区间使和最大。暴力枚举左右端点O(n²)不可行但如果你先算出前缀和s那么区间[l, r]的和就是s[r] - s[l-1]想让这个差值最大只需在遍历一遍的过程中维护前面出现过的最小s值然后用当前s[r]减去那个最小值更新答案。这是O(n)的做法核心武器依然是前缀和。还有一类“求数组中有多少个子数组的和等于k”的问题遍历前缀和的同时用哈希表记录每个前缀和值出现的次数每次找当前s[i] - k出现过多少次。这类“前缀和 哈希表”的组合拳在竞赛和面试里都非常高频。记住前缀和的价值不是“算一个区间和”而是把“区间”变成“两个前缀的差值”后者的信息量更大也更方便做各种变形。3. 差分数组区间操作的高效化3.1 差分数组怎么构造差分数组的定义一句话d[i] a[i] - a[i-1]。它记录的是原数组每一位相对于前一位的变化量。比如原数组a [0, 3, 5, 9, 2]从下标1开始差分数组就是d[1]3d[2]2d[3]4d[4]-7。构造代码直接按定义写vectorlong long a(n 1), d(n 2); for (int i 1; i n; i) { cin a[i]; d[i] a[i] - a[i-1]; }但还有一种更推荐的构造方式把“初始化”也当成一次区间操作。原数组可以看作从全0数组开始对每个下标i执行一次“在区间[i, i]上加a[i]”的操作。于是可以这样写vectorlong long d(n 2); for (int i 1; i n; i) { long long x; cin x; d[i] x; d[i 1] - x; }第二种写法从第一步就训练你“用差分思维”思考后面遇到任何区间加操作都往同一个模板套不容易乱。注意数组长度开到n2因为i等于n时会访问d[n1]这是个很常见的越界点。3.2 区间加为什么一次只改两个位置现在看最关键的问题为什么给区间[l, r]加上v只需要改d[l]和d[r1]两个位置先回顾差分数组的性质对差分数组做前缀和就能还原原数组。也就是说原数组每个位置的值是差分数组从第1个位置累加到该位置的结果。那么如果我在d[l]位置加上v从l开始往后所有前缀和结果都会凭空多出v但我不希望r之后的元素受到影响所以还要在d[r1]位置减去v这样前缀和从r1开始加的v又被抵消了正好恢复成原来的值。拿一条水管来类比d数组的每个位置是两个阀门在l处打开注入v水流顺着管道一路流到r在r1处再开一个排水口把v排掉这样r后面的水管里的水位不变。这个“标记起点、标记终点之后”的模式就是差分区间加的全部秘密。// 区间加模板把[l, r]内所有数加v d[l] v; d[r 1] - v;等所有操作都完成后对d做一次前缀和输出每个位置的最终值for (int i 1; i n; i) { d[i] d[i - 1]; // 此时d[i]就是原数组a[i]的最终值 cout d[i] ; }3.3 二维差分四个标记点原理不复杂二维差分比一维只多一层维度但很多新手一看四个点就头皮发麻。其实它就是一个二维版的“起点加水、终点排水”。假设你有一个n行m列的矩阵现在要把以(x1,y1)为左上角、(x2,y2)为右下角的矩形区域内所有元素都加v。一维差分改两个点二维差分就要改四个点d[x1][y1] v; d[x2 1][y1] - v; d[x1][y2 1] - v; d[x2 1][y2 1] v;然后对整个差分矩阵做二维前缀和得到的就是更新后的原矩阵。for (int i 1; i n; i) for (int j 1; j m; j) d[i][j] d[i-1][j] d[i][j-1] - d[i-1][j-1];为什么是这四个点你可以把二维前缀和想象成“从左上角开始累加”。d[x1][y1]加v会让以(x1,y1)为起点、向右向下无限延伸的整个矩形区域都带上v这太大范围了。为了只保留一块指定矩形需要在右下边界之外“拦住”于是(x21, y1)减v把向下继续扩散的部分消掉(x1, y21)减v把向右扩散的部分消掉。但这两刀切下去右下角那块(x21, y21)被减了两次所以还要加回一次v。这个逻辑和二维前缀和的容斥完全一样理解了容斥四个点就不会记错。4. 前缀和与差分组合实战4.1 高频组合区间加操作区间和查询单独用差分能解决“多次区间加、最后求一次原数组”的问题单独用前缀和能解决“查询很多次区间和、但数组不变”的问题。但如果题目说先给一个数组然后有多次操作每次把某个区间的数加v过程中或结束后你还需要反复查询某些区间的和。这时候两种工具就要一起上阵了。最标准的流程是先用差分记录所有的区间加操作等所有修改都结束后对差分数组求一次前缀和得到每个位置的最终值接着再对这个最终值数组求一次前缀和用它来回答所有区间和查询。下面是一个典型的完整代码骨架#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorlong long a(n 1), diff(n 2); for (int i 1; i n; i) { cin a[i]; diff[i] a[i]; diff[i 1] - a[i]; } // 模拟区间加操作 while (q--) { int l, r; long long v; cin l r v; diff[l] v; diff[r 1] - v; } // 第一次前缀和从差分恢复原数组 for (int i 1; i n; i) { a[i] a[i - 1] diff[i]; } // 第二次前缀和用于快速区间查询 vectorlong long s(n 1); for (int i 1; i n; i) { s[i] s[i - 1] a[i]; } int queryTimes; cin queryTimes; while (queryTimes--) { int l, r; cin l r; cout s[r] - s[l - 1] \n; } return 0; }这套流程在竞赛里太常见了它处理的是静态数组上的批量区间修改加多次区间查询。每次区间加只要O(1)每次查询只要O(1)整体复杂度O(nq)性能极佳。4.2 特殊变形乘法和混合操作怎么处理有的题目不止区间加法还有区间乘法。这时候直接套差分数组会失效因为乘法和加法的累积规则不一样。我的建议是先判断操作是否“线性可叠加”。如果既有加法又有乘法常见做法是把乘法拆成“乘的全部因子”和“加的部分”分别记录或者干脆上线段树。这里不展开线段树只提醒一句差分和前缀和最擅长处理加法型操作遇到乘法型操作不要硬套不然很容易得到错误结果。还有一类经典题给若干个区间统计每个位置被覆盖了多少次。解法就是用差分每次出现一个区间[l, r]就执行d[l], d[r1]--最后做一次前缀和每个位置的值就是覆盖次数。比如很多“公交车上下车人数统计”“同时在线人数最大峰值”问题本质都是这个套路。这类题目是差分最漂亮的出场方式因为它把“区间覆盖”抽象成了两个端点标记整个统计过程变成一次线性扫描。我见过很多人拿到这类题会用区间树或扫描线去解绕了一圈结果发现差分加一趟循环就够了。4.3 要注意的扩展树状数组与线段树当你看到题目里的操作不是“先全部改完再全部查询”而是“改一步、查一步、改一步、查一步”这种动态交替进行时纯前缀和加差分就有点不够用了。每次修改都会影响后续所有前缀和的结果你不得不重新做前缀和那复杂度又回去了。这时候需要引入树状数组或线段树这样的动态数据结构。树状数组可以看作是支持单点修改、前缀和查询的动态版前缀和它能在O(log n)时间里完成每次更新和每次求前缀和。如果你已经理解了前缀和是“统计信息的累加视图”树状数组的优势就是让这个视图能随时更新。差分也可以和树状数组结合实现“区间加、单点查询”的动态版本这算是一种很自然的进阶路径。很多选手的成长路线就是先吃透前缀和和差分再过渡到树状数组最后是线段树。这个顺序是有道理的因为树状数组的某些思路正式从“差分前缀和”的变形里长出来的。5. 常见问题与排查技巧5.1 下标从0开始还是从1开始前缀和与差分模板里我强制要求自己从下标1开始用。原因只有一个差分的区间操作要访问d[r1]如果下标从0开始当r等于n-1时r1会访问到d[n]数组长度比较尴尬更重要的是前缀和查询公式s[r] - s[l-1]如果l等于0会出现s[-1]这种非法下标。用1-based下标s[0]和d[0]天然是0相当于一个不存在的空元素边界情况就不需要if判断了。很多新手一开始习惯从0开始写出来的代码总要多判几个边界写成从1开始之后代码瞬间清爽很多。别小看这个习惯它在二维情况里价值更大能帮你省掉一堆坐标越界的麻烦。5.2 数值溢出是必踩的坑前缀和和数据量一大数值就会快速膨胀。n10万每个数最大10万前缀和最多到10^10int根本装不下。差分数据看似只记差值但如果初始值和增加量都很大累加过程中同样可能溢出。我从学这个知识点第一天就被告诫用long long可自己还是在大一比赛里因为贪图省事用int导致WA了半天最后查出来是溢出那次教训特别深刻。现在的惯例是只要不是题目明确说明输入范围很小一律vector 。代码多几个字母换来的是一晚上的睡眠。5.3 数组长度和越界问题差分数组一定要开成n2而不是n1。原因很简单区间[l, r]加v时如果r等于n你要访问d[n1]而n1这个位置需要真实存在。另外构造差分时也有同样的需求。数组长度不够并不会直接报错它会安静地越界修改相邻内存产生一个特别难查的奇怪结果。我自己的经验是写差分类的模板时直接在定义旁边写一行注释“// 长度为n2因为需要访问r1”。还有一个容易忽略的细节做完差分之后如果还要在原始数组基础上继续用不要直接把差分数组当成最终数组返回而是先复制一份原始值再做区间操作。否则多次重复做前缀和数值会成倍增长结果完全扭曲。5.4 不要把差分和前缀和背成孤立模板我见过太多人把前缀和和差分当成两个独立模板来背考场上遇到需要几步组合就用得不顺畅。实际上它们的联系很简单差分数组的前缀和就是原数组原数组的前缀和就是能回答区间和查询的数据。你自己动手在纸上画一个只有5个元素的数组先写出它的差分再对差分做前缀和把中间过程都列出来你会亲眼看到它们是如何互相转换的。这一步比背任何代码都管用。另外一个排查技巧无论用前缀和还是差分写完代码后先用一个极小的示例比如n5操作3次手算一遍把期望输出打印出来比对。这类题的样例一般都覆盖边界跑一遍就能发现下标错误和越界问题。写到这里关于前缀和与差分的基本功就算扎实了。我个人在实际操作中的体会是千万不要把这两个知识点仅仅当模板去刷而是要把它们当成一对“互逆的视角”看到区间更新想差分看到区间查询想前缀和看到同时需要两者就想怎么把差分的结果再喂给前缀和。这套思路一旦建立起来后面无论是走信奥路线还是面试刷题遇到区间类的题目都会特别有底气。如果你接下来打算接触树状数组或者线段树也可以带着“这不就是动态差分加上可更新的前缀和吗”这种念头去学会发现后面的路顺畅不少。