如果你在 C 语言里处理过“区间增减”这种操作大概能体会到那种看着简单、跑起来却特别憋屈的感觉一组长度为十万的数组来上十万次区间修改随便一个两层循环就把时间跑穿了。我最早碰到这个问题时第一个念头就是老老实实 for 一遍结果被数据规模教做人。后来学会了差分数组才明白原来“区间整体加一个数”这种高频操作根本不需要碰区间里的每个元素。差分数组的核心思路就一句话用相邻元素的差值去表示原数组把一次区间修改变成两个单点修改。它特别适合正在学 C 语言、刷算法题或者想优化数组批量操作性能的读者。掌握了它很多“多次区间增减、最后再来查询”的题目复杂度能从 O(n*m) 直接降到 O(nm)而且代码量不到三十行比线段树友好太多了。1. 为什么说差分数组是区间增减的“快车道”1.1 暴力写法为什么会被卡先看一个最常见的需求。给你一个长度为 n 的数组 a然后来 m 次操作每次操作给下标从 L 到 R 的这段区间统一加上一个数 c最后要求输出整个数组。很多人第一版代码会写成这样for (int i l; i r; i) { a[i] c; }这段代码本身没有任何语法错误逻辑也对。问题是它被放在了一个更大的循环里外面还有 m 次操作。当 n 和 m 都是 10^5 时最坏情况要执行 10^10 次加法。哪怕一次加法只需要一纳秒也要十秒以上而 OJ 上的时间限制通常只有一秒。不是编译器不够快是算法复杂度摆在那里。暴力写法慢在“每个元素都被反复访问”。区间越大、操作越多重复工作量就越大。如果只是修改一次暴力完全没问题可怕的是高频修改同一个区间比如 10 万次操作都落在同一个长区间暴力的耗时就会变成灾难。很多人一开始觉得“C 语言循环这么快应该没问题吧”实际上到了 10^5 这个量级循环次数已经不是快不快的问题而是算法层级的差距。1.2 差分数组到底在做什么差分数组的核心思想是不直接改原数组而是去维护原数组“相邻位置之间的差值”。这个差值就叫差分值。原数组中一段区间同时加同一个数区间内部任何相邻两个元素都同时增加相同数值它们的差值完全不变。变的只有两个位置区间起点以及区间终点后面那个位置。所以一次区间增减就变成了两个单点修改。拿排队领东西举例。正常做法是给队伍里每个人都发一份差分做法是在队首挂一块牌子“从这里开始每人加一份”在队尾后面也挂一块牌子“到这里结束”。不需要碰中间每一个人最后从队首走到队尾结算一次就能知道每个人手里是多少。这个类比就是差分数组的工作过程更新时只改端点查询或输出时从头到尾做一次前缀和。用一句更准确的话说差分是前缀和的逆运算原数组是差分数组的“积分结果”。1.3 什么场景用它最合适差分数组适合解决“离线”的区间修改问题。所谓离线就是所有操作都做完以后你才去查最终结果。常见的适合场景有多次执行区间增减操作最后输出整个数组。多次执行区间增减操作最后只查询某个点的值。批量处理二维矩阵的矩形区域增减再用二维前缀和还原。统计多个区间覆盖后每个点被覆盖了多少次。不适合的场景也很明确每操作一次立刻查询某个区间的和。区间内每个位置加的值不同不是统一增量。需要动态插入、删除元素并且随时维护整体信息。遇到后面这些情况就换树状数组、线段树或者更复杂的数据结构别硬套差分数组。2. 一维差分数组的原理推导从公式到边界2.1 差分是前缀和的逆运算如果你熟悉前缀和学差分会非常顺。前缀和 pre[i] pre[i-1] a[i]它把原数组的“增量”累积成“总和”差分 d[i] a[i] - a[i-1] 则反过来它把原数组拆成“变化量”。两个操作互为逆运算。假设数组下标从 1 开始并且 a[0] 0那么d[1] a[1] - a[0] d[2] a[2] - a[1] ... d[i] a[i] - a[i-1]把这些式子累加一下d[1] d[2] ... d[i] (a[1] - a[0]) (a[2] - a[1]) ... (a[i] - a[i-1]) a[i] - a[0] a[i]这就是差分的还原公式对差分数组求一遍前缀和就得到原数组。所以差分数组和前缀和经常成对出现先用差分记录变化再用前缀和还原结果。也许你会问既然手里已经有原数组为什么还要多存一份差距因为差距更能反映“变化”。区间增减时原数组可能要修改很多个位置但差距只在端点处变化。这种从“绝对值”转向“变化量”的视角是很多高效算法的共同思路。2.2 区间加为什么只改两个位置设区间 [l, r] 整体加上 v。我们逐个看差分值的变化。先看 l 位置。原来的 d[l] a[l] - a[l-1]修改后 a[l] 变成 a[l]v而 a[l-1] 没有变所以 d[l] 增加了 v。再看中间位置 i ∈ (l, r]。a[i] 和 a[i-1] 都同时加了 v差值 a[i]-a[i-1] 不变所以 d[i] 不变。最后看 r1 位置。原来的 d[r1] a[r1] - a[r]修改后 a[r1] 没变a[r] 变成 a[r]v差值减少了 v所以 d[r1] 减少了 v。结论一句话对原数组 [l, r] 加 v等价于对差分数组执行 d[l] vd[r1] - v。举个例子。原数组 a {1, 3, 5, 9, 4}差分数组是 d {1, 2, 2, 4, -5}。现在把下标 1 到 3 整体加 2得到新数组 a {3, 5, 7, 9, 4}。按差分做法d[1] 2 得到 3d[4] - 2 得到 2差分数组变成 {3, 2, 2, 2, -5}。再对差分数组求前缀和3、5、7、9、4完美还原。2.3 边界条件与数组长度的坑最容易被坑的地方是 r n 的时候。如果区间右端到达数组末尾那么 d[r1] 就是 d[n1]而原数组 a 只有 n 个元素。这时候如果你只开了一个长度为 n 的数组执行 d[r1] - v 就会越界。解决办法有两种。第一种是在代码里加一个判断if (r 1 n) { d[r 1] - v; }第二种是把数组长度多开两个位置直接写 d[r 1] - v不做任何判断。我强烈推荐第二种理由有两个少写一个 if代码更干净d[n1] 作为一个“哨兵位置”在还原时根本不会被遍历到但它能安全承接 r n 的情况。顺便说一句下标风格。如果用 1-based 下标a[0] 当哨兵区间 [l, r] 更新就是 d[l] vd[r1] - v。如果用 0-based 下标区间 [l, r] 更新时同样要写 d[l] vd[r1] - v但如果 r1 n就必须加 if 判断。所以我个人在 C 语言里处理这类问题几乎一律用 1-based 下标省心很多。3. C语言实现实战写一个能跑的区间增减程序3.1 下标设计0-based还是1-based在 C 语言里数组天然是 0-based很多初学者习惯从 0 开始。但对于区间操作题目我建议换个思路从 1 开始存数据。原因很简单输入数据通常给的是 1-based 的 L 和 R。如果你内部也用 1-based输入后直接就能用不需要做 l--、r-- 的转换。更关键的是a[0] 可以留作 0 哨兵d[r1] 在 rn 时也有一位合法的数组空间。相比之下0-based 的边界处理要复杂一些还容易漏掉 r1n 的越界判断。所以我的习惯是这样long long a[MAXN], d[MAXN];其中 MAXN 比题目要求的最大 n 多开 5 个比如 n 100000 就开 100005。这样 d[n1] 一定存在r1 越界的风险几乎为零。3.2 完整代码与输入输出示例下面是一份可以直接运行的 C 语言代码处理“给定初始数组m 次区间加最后输出完整数组”的问题。#include stdio.h #define MAXN 100005 long long a[MAXN], d[MAXN]; int main() { int n, m; scanf(%d %d, n, m); for (int i 1; i n; i) { scanf(%lld, a[i]); d[i] a[i] - a[i - 1]; } while (m--) { int l, r; long long v; scanf(%d %d %lld, l, r, v); d[l] v; d[r 1] - v; } long long cur 0; for (int i 1; i n; i) { cur d[i]; a[i] cur; printf(%lld%c, a[i], i n ? \n : ); } return 0; }输入数据5 2 1 3 5 9 4 1 3 2 2 4 -1执行过程如下初始数组 a {1, 3, 5, 9, 4}d {1, 2, 2, 4, -5}第一次操作 [1,3] 加 2d[1] 2d[4] - 2得到 d {3, 2, 2, 2, -5}第二次操作 [2,4] 减 1d[2] - 1d[5] 1得到 d {3, 1, 2, 2, -4}最终前缀和还原3、4、6、8、4输出3 4 6 8 4这里我用 long long而不是 int。理由后面会专门讲先记住一点涉及连续区间累加int 很容易溢出。3.3 多组数据和初始化细节很多 OJ 题目都有多组测试数据这时最容易翻车的地方是差分数组的初始化。假设你把 d 数组开成全局变量第一次运行之前它会自动清零但第二组数据来的时候上一组残留的 d[n1] 可能还会影响结果。正确做法是每组数据开始前把 d[0] 到 d[n1] 全部清零for (int i 0; i n 1; i) { d[i] 0; }如果你习惯用 memset可以写成memset(d, 0, sizeof(long long) * (n 2));注意不要写 memset(d, 0, sizeof(d)) 然后还觉得万事大吉。虽然这样也能清整个数组但如果你把 MAXN 开得很大而每组数据实际 n 很小清整个数组会浪费不少时间。更推荐只清需要用到的部分。还有一个小细节因为构造 d[i] a[i] - a[i-1] 用到了 a[i-1]所以 a[0] 必须保证是 0。全局数组会自动初始化为 0但如果你把 a 定义在函数内部记得手动给 a[0] 0。如果题目本来就是“初始全 0后面 m 次区间加”那就更简单了。连构造差分的步骤都可以省掉直接每次更新 d[l] vd[r1] - v最后一遍前缀和还原。这种写法在很多练习题里非常常见。4. 进阶扩展二维差分与算法选型4.1 二维差分怎么推导和编码一维差分解决的是“线段”上的区间增减二维差分解决的是“矩形”上的区域增减。比如给你一个 n 行 m 列的矩阵q 次操作每次把左上角 (x1, y1) 到右下角 (x2, y2) 的矩形区域统一加上 v最后输出整个矩阵。二维差分的定义是d[i][j] a[i][j] - a[i-1][j] - a[i][j-1] a[i-1][j-1]这其实是二维前缀和的逆运算。矩形区域加 v 时只需要更新四个位置d[x1][y1] v; d[x2 1][y1] - v; d[x1][y2 1] - v; d[x2 1][y2 1] v;最后对 d 数组做一遍二维前缀和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[i][j] 的值就是原矩阵经过所有矩形更新后的最终值。二维差分的四个端点可以理解成“矩形的四个角”进入矩形加离开矩形减角落位置由于同时影响横纵两个方向需要额外补偿。如果一维差分已经理解透彻二维差分只是把“两个端点”扩展成了“四个端点”。4.2 差分数组、树状数组、线段树怎么选很多初学者学会差分数组之后会想“是不是所有区间问题都可以用差分”答案是否定的。我给自己整理过一个选型逻辑你可以参考方法区间更新区间查询在线能力实现成本差分数组O(1)还原 O(n)还原后查询 O(1)只适合离线最低树状数组O(log n)O(log n)支持在线中等线段树O(log n)O(log n)支持在线较高这里的“在线”是指每次操作完成后马上要查询。如果题目要求每加完一次就问你某个区间的和差分数组是不行的因为每次查询都需要重新求前缀和复杂度变成 O(nm)。这时候用树状数组维护差分或者直接上线段树加懒标记才是正确方向。反过来如果题目只要求所有操作结束之后输出最终数组那就没必要搬出线段树。差分数组代码短、常数小、不容易写错是这类场景的最优解。4.3 差分数组还能玩出什么花差分数组不只是用来“区间加再还原”它的思想还能扩展到很多场景。一个很经典的应用是求区间覆盖次数。你把每个区间 [l, r] 都当成一次“覆盖操作”执行 d[l] 1d[r1] - 1最后求一遍前缀和每个位置的值就是它被多少个区间覆盖。这在处理多个货物区间、多个日程安排、多种资源占用的问题时非常好用。另一个扩展是配合扫描线求所有区间操作后的最大值。你不需要把完整数组存下来再二次扫描而是在还原前缀和的过程中顺便维护最大值。这样空间不变时间也只是 O(n)。如果你遇到的是“区间内依次加上一个等差数列”比如从左到右加 1、2、3、...那一阶差分就不够了需要用二阶差分。思路仍然是从“变化量”出发只不过这次要维护“变化量的变化量”。有兴趣的话可以自己推一下公式和二维差分的推导方式很类似。5. 常见问题排查与避坑心得5.1 数组越界r1 这个魔鬼细节差分数组最常见的问题就是越界。很多同学写完代码本地测试小数据没问题一提交就莫名其妙 WA 或者 Runtime Error找了半天发现是 d[r1] 越界。我调试过的一个真实案例是n 5数组只开了 5 个元素某次操作正好 r 5。代码执行 d[6] - v写到了数组外面的内存。程序没立刻崩但把相邻变量的值改坏了最后输出结果完全不对。用 gdb 看变量时才发现一个无关变量的值被改成了很奇怪的东西。所以从现在开始凡是和差分擦边的数组我都建议至少开MAXN 2个元素。这是最低成本的保险能帮你把注意力集中在算法逻辑上而不是浪费在边界 debug 上。5.2 数据溢出int 让你“莫名其妙WA”差分数组的更新都是 O(1)但你架不住操作次数多。举个例子n 100000m 100000每次区间加的值 v 1000000000最后一次前缀和累加时cur 很容易超过 10^14。这个数远远超过 int 能表示的约 21 亿。我见过不少选手算法思路完全正确就是因为用了 int导致最终数组变成负数或者奇怪的数字交上去 WA 得莫名其妙。解决方式只有两个字long long。所有相关变量包括数组、差分数组、单次操作的值统一用 long long。除非题目明确告诉你答案在 int 范围内否则不要赌。这里还要注意 scanf 和 printf 的格式符。long long 用%lld不是%d。这个错误看起来低级但在紧张的比赛环境下真的很容易发生。5.3 用暴力对拍调试差分数组如果你写的差分代码在小数据上就出错最快的定位方法不是盯代码发呆而是写一个暴力版本对拍。先在代码里写一个暴力函数void brute(int a[], int n, int ops[][3], int m) { for (int i 0; i m; i) { int l ops[i][0], r ops[i][1], v ops[i][2]; for (int j l; j r; j) { a[j] v; } } }再写一个差分版本用随机生成器造小数据n 不超过 10m 不超过 10l、r 随机v 可以为负数。两个函数各自跑一遍比较最终数组。只要有一组不一样就打印输入、暴力结果和差分结果很快就能看出是边界处理错还是初始化错。这个对拍方法不需要任何额外工具一个 C 文件里就能完成。我每次写这类题都会先跑一轮随机小数据对拍再提交几乎不会翻车。5.4 个人踩坑后的习惯最后分享几个我自己总结出来的习惯给同样在学 C 语言和算法的朋友参考。第一所有数值默认用 long long。除非题目明确说 int 范围够用否则我不为了省一点内存去赌溢出。第二数组永远多开两个位置。d[n1] 不是浪费而是安全哨兵。尤其差分数组的 r1 操作多开两个位置能让你省掉一堆 if。第三下标统一从 1 开始。a[0] 当 0 哨兵公式推导和代码实现都更顺思维方式也更统一。第四写完先跑小数据手算再跑随机对拍最后再提交。尤其是第一次用差分数组时边界很容易出错跑对拍能帮你快速建立正确的“边界感”。第五不要路径依赖。看到区间操作就只想到差分数组看到区间最大值就只想到线段树。数据结构选型要根据“在线还是离线”“查什么”“改什么”来综合判断。差分数组是很好用但它不是万能药。我在实际写代码的过程中差分数组是使用频率最高的数据结构之一。它足够简单简单到几十行就能写完它又足够强大强大到能把 10^5 量级的区间操作问题变成接近线性的复杂度。希望这篇实战笔记能帮你真正掌握这个“高效玩法”。