企业官网建设流程全解析

如果你在 C 语言里处理过“区间增减”这种操作，大概能体会到那种看着简单、跑起来却特别憋屈的感觉：一组长度为十万的数组，来上十万次区间修改，随便一个两层循环就把时间跑穿了。我最早碰到这个问题时，第一个念头就是老老实实 for 一遍，结果被数据规模教做人。后来学会了差分数组，才明白原来“区间整体加一个数”这种高频操作，根本不需要碰区间里的每个元素。

差分数组的核心思路就一句话：用相邻元素的差值去表示原数组，把一次区间修改变成两个单点修改。它特别适合正在学 C 语言、刷算法题，或者想优化数组批量操作性能的读者。掌握了它，很多“多次区间增减、最后再来查询”的题目，复杂度能从 O(n*m) 直接降到 O(n+m)，而且代码量不到三十行，比线段树友好太多了。

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] 不变。

最后看 r+1 位置。原来的 d[r+1] = a[r+1] - a[r]，修改后 a[r+1] 没变，a[r] 变成 a[r]+v，差值减少了 v，所以 d[r+1] 减少了 v。

结论一句话：对原数组 [l, r] 加 v，等价于对差分数组执行 d[l] += v，d[r+1] -= 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 得到 3，d[4] -= 2 得到 2，差分数组变成 {3, 2, 2, 2, -5}。再对差分数组求前缀和：3、5、7、9、4，完美还原。

2.3 边界条件与数组长度的坑

最容易被坑的地方是 r = n 的时候。如果区间右端到达数组末尾，那么 d[r+1] 就是 d[n+1]，而原数组 a 只有 n 个元素。这时候如果你只开了一个长度为 n 的数组，执行 d[r+1] -= v 就会越界。

解决办法有两种。第一种是在代码里加一个判断：

if (r + 1 <= n) { d[r + 1] -= v; }

第二种是把数组长度多开两个位置，直接写 d[r + 1] -= v，不做任何判断。我强烈推荐第二种，理由有两个：少写一个 if，代码更干净；d[n+1] 作为一个“哨兵位置”，在还原时根本不会被遍历到，但它能安全承接 r = n 的情况。

顺便说一句下标风格。如果用 1-based 下标，a[0] 当哨兵，区间 [l, r] 更新就是 d[l] += v，d[r+1] -= v。如果用 0-based 下标，区间 [l, r] 更新时同样要写 d[l] += v，d[r+1] -= v，但如果 r+1 == 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[r+1] 在 r=n 时也有一位合法的数组空间。相比之下，0-based 的边界处理要复杂一些，还容易漏掉 r+1==n 的越界判断。

所以我的习惯是这样：

long long a[MAXN], d[MAXN];

其中 MAXN 比题目要求的最大 n 多开 5 个，比如 n <= 100000 就开 100005。这样 d[n+1] 一定存在，r+1 越界的风险几乎为零。

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] 加 2：d[1] += 2，d[4] -= 2，得到 d = {3, 2, 2, 2, -5}
• 第二次操作 [2,4] 减 1：d[2] -= 1，d[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[n+1] 可能还会影响结果。

正确做法是每组数据开始前，把 d[0] 到 d[n+1] 全部清零：

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] += v，d[r+1] -= 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(nm)。这时候用树状数组维护差分，或者直接上线段树加懒标记，才是正确方向。

反过来，如果题目只要求所有操作结束之后输出最终数组，那就没必要搬出线段树。差分数组代码短、常数小、不容易写错，是这类场景的最优解。

4.3 差分数组还能玩出什么花

差分数组不只是用来“区间加再还原”，它的思想还能扩展到很多场景。

一个很经典的应用是求区间覆盖次数。你把每个区间 [l, r] 都当成一次“覆盖操作”，执行 d[l] += 1，d[r+1] -= 1，最后求一遍前缀和，每个位置的值就是它被多少个区间覆盖。这在处理多个货物区间、多个日程安排、多种资源占用的问题时非常好用。

另一个扩展是配合扫描线，求所有区间操作后的最大值。你不需要把完整数组存下来再二次扫描，而是在还原前缀和的过程中顺便维护最大值。这样空间不变，时间也只是 O(n)。

如果你遇到的是“区间内依次加上一个等差数列”，比如从左到右加 1、2、3、...，那一阶差分就不够了，需要用二阶差分。思路仍然是从“变化量”出发，只不过这次要维护“变化量的变化量”。有兴趣的话，可以自己推一下公式，和二维差分的推导方式很类似。

5. 常见问题排查与避坑心得

5.1 数组越界：r+1 这个魔鬼细节

差分数组最常见的问题就是越界。很多同学写完代码本地测试小数据没问题，一提交就莫名其妙 WA 或者 Runtime Error，找了半天发现是 d[r+1] 越界。

我调试过的一个真实案例是：n = 5，数组只开了 5 个元素，某次操作正好 r = 5。代码执行 d[6] -= v，写到了数组外面的内存。程序没立刻崩，但把相邻变量的值改坏了，最后输出结果完全不对。用 gdb 看变量时，才发现一个无关变量的值被改成了很奇怪的东西。

所以从现在开始，凡是和差分擦边的数组，我都建议至少开MAXN + 2个元素。这是最低成本的保险，能帮你把注意力集中在算法逻辑上，而不是浪费在边界 debug 上。

5.2 数据溢出：int 让你“莫名其妙WA”

差分数组的更新都是 O(1)，但你架不住操作次数多。举个例子，n = 100000，m = 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 不超过 10，m 不超过 10，l、r 随机，v 可以为负数。两个函数各自跑一遍，比较最终数组。只要有一组不一样，就打印输入、暴力结果和差分结果，很快就能看出是边界处理错，还是初始化错。

这个对拍方法不需要任何额外工具，一个 C 文件里就能完成。我每次写这类题，都会先跑一轮随机小数据对拍，再提交，几乎不会翻车。

5.4 个人踩坑后的习惯

最后分享几个我自己总结出来的习惯，给同样在学 C 语言和算法的朋友参考。

第一，所有数值默认用 long long。除非题目明确说 int 范围够用，否则我不为了省一点内存去赌溢出。

第二，数组永远多开两个位置。d[n+1] 不是浪费，而是安全哨兵。尤其差分数组的 r+1 操作，多开两个位置能让你省掉一堆 if。

第三，下标统一从 1 开始。a[0] 当 0 哨兵，公式推导和代码实现都更顺，思维方式也更统一。

第四，写完先跑小数据手算，再跑随机对拍，最后再提交。尤其是第一次用差分数组时，边界很容易出错，跑对拍能帮你快速建立正确的“边界感”。

第五，不要路径依赖。看到区间操作就只想到差分数组，看到区间最大值就只想到线段树。数据结构选型要根据“在线还是离线”“查什么”“改什么”来综合判断。差分数组是很好用，但它不是万能药。

我在实际写代码的过程中，差分数组是使用频率最高的数据结构之一。它足够简单，简单到几十行就能写完；它又足够强大，强大到能把 10^5 量级的区间操作问题变成接近线性的复杂度。希望这篇实战笔记，能帮你真正掌握这个“高效玩法”。