什么是差分？——批量修改数据的快捷方法

假如你的老师想给全班同学的考试成绩都加上5分，或者只给第3名到第8名的同学加5分，你会怎么做？如果一个个修改，人数多了很慢。今天我们来学习差分，它就像一把“魔法刷子”，可以快速给数组的一大段区域统一添加或减少同一个数。

为什么要用差分？

想象你要给一个长长的数组反复做“区间加”操作：比如给第2到第5个元素加3，接着给第4到第7个元素减2，再给第1到第10个元素加1……如果用最笨的办法，每次循环遍历区间里的每个数，当数组大小是 $10^5$ 、操作次数也是 $10^5$ 时，总时间就是 $10^{10}$ 次，电脑会慢到崩溃。而差分只需要两次修改，再求一次前缀和就能完成一次区间操作，速度飞快！它特别适合“多次、对连续区间统一加减”的场景。

什么是差分？——差分数组的定义

差分是前缀和的好朋友，但方向相反。我们用一个数组 diff 来表示原数组 a 中相邻两个数的差：

diff[1] = a[1] - 0（习惯上认为 a[0] = 0，所以 diff[1] = a[1]）
diff[2] = a[2] - a[1]
diff[3] = a[3] - a[2]
……
diff[n] = a[n] - a[n-1]

用一句话说：差分数组记录的是数组中每个位置相对于前一个位置的变化量。

例如，原数组 a = [2, 5, 3, 7]（下标从1开始），那么：

diff[1] = 2 - 0 = 2
diff[2] = 5 - 2 = 3
diff[3] = 3 - 5 = -2
diff[4] = 7 - 3 = 4

所以差分数组就是 diff = [2, 3, -2, 4]。注意，差分数组的长度和原数组一样，但我们通常还会多开一个位置 diff[n+1]，用来处理区间终点之后的下标。

区间修改的原理——只需两步操作

神奇的是，如果你想把原数组从第 l 个到第 r 个元素都加上一个数 x，只需要做两个操作：

diff[l] += x
diff[r+1] -= x

然后对差分数组求一遍前缀和，就能得到修改后的原数组。为什么这样有效？因为差分数组记录了变化，而前缀和可以恢复原样。

用积木例子理解

想象一下：你有一排积木，高度分别是 [2, 5, 3, 7]。你想让第2块到第3块积木都加高2厘米。如果用差分，你只需要在 diff[2] 加2，在 diff[4] 减2，最后再求一遍前缀和，积木高度就变成了 [2, 7, 5, 7]。是不是很快？

让我们一步步来：

初始差分：diff = [2, 3, -2, 4]（下标1~4）
执行操作：l=2, r=3, x=2
- diff[2] += 2 → diff[2] 变成 5
- diff[4] -= 2 → diff[4] 变成 2
此时 diff = [2, 5, -2, 2]
求前缀和恢复 a：
- new_a[1] = 0 + diff[1] = 2
- new_a[2] = 2 + diff[2] = 7
- new_a[3] = 7 + diff[3] = 5
- new_a[4] = 5 + diff[4] = 7
结果：[2, 7, 5, 7]，正好第2、3块加了2！

用生活例子理解——发零花钱

假设你每周记录自己存的钱（零花钱减去花掉的），数组 a 表示每天结束时钱包里的钱数。某天妈妈突然说：“第3天到第7天，每天多给你5元。”如果用差分，你只需要在 diff[3] 加5（表示从这天开始多5元），在 diff[8] 减5（表示第8天恢复原样）。然后重新累加，就能得到每天正确的钱数。这样做，不管区间多长，都只需要修改两个位置。

差分与前缀和的关系

前缀和是从数组首尾累加得到总和，差分则是反过来求相邻差值。它们互为逆运算：

对原数组求前缀和 → 得到前缀和数组
对原数组求差分 → 得到差分数组
对差分数组求前缀和 → 恢复原数组
对前缀和数组求差分 → 恢复原数组

所以经常把差分和前缀和放在一起学，一个负责区间修改，一个负责区间查询。掌握了它们，很多算法题做起来就轻松多了。

多次区间修改的例子

差分最厉害的地方在于，它可以把多次区间修改叠加起来。你只需要记录每次修改的两个变化量，最后统一求一次前缀和即可。下面用考试成绩的例子演示：

小明班上有10个同学，初始成绩 a = [70, 80, 90, 85, 75, 60, 95, 88, 92, 78]（下标1~10）。老师做了三次操作：

第1~5名每人加3分（表扬）
第4~8名每人减2分（扣分项目）
第2~9名每人加5分（附加题加分）

我们希望得到最终成绩。用差分做，只需要：

构建初始差分数组 diff（基于初始成绩）
第一次：diff[1] += 3，diff[6] -= 3
第二次：diff[4] -= 2，diff[9] += 2
第三次：diff[2] += 5，diff[10] -= 5
最后对 diff 求前缀和，得到最终成绩

完整代码见下一节。

完整可运行的示例代码

下面的代码演示了如何用差分实现多次区间修改。代码中有详细的注释，变量名使用简短英文单词，每行变量定义后跟着中文注释。

#include <iostream>
using namespace std;

int main() {
    int a[100], diff[100];  // 原数组和差分数组，下标从1开始
    int n;                  // 数组大小
    cout << "请输入数组大小：";
    cin >> n;

    // 读入原数组
    cout << "请输入" << n << "个整数：";
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 构建差分数组
    diff[1] = a[1];                 // 假设 a[0] = 0
    for (int i = 2; i <= n; i++) {
        diff[i] = a[i] - a[i-1];    // 相邻差
    }
    // 注意：diff[n+1] 初始为0（也可以不设置，但后续会用到）

    // 进行多次区间加操作
    int m;  // 操作次数
    cout << "请输入操作次数：";
    cin >> m;
    for (int op = 1; op <= m; op++) {
        int l, r, x;                // 区间左、右端点，加的数
        cout << "第" << op << "次操作（l r x）：";
        cin >> l >> r >> x;

        // 核心两步
        diff[l] += x;
        diff[r+1] -= x;             // 注意 r+1 可能越界，数组要开大一点
    }

    // 通过前缀和恢复修改后的数组
    int new_a[100];                 // 存储修改后的数组
    new_a[0] = 0;                   // 前缀和起点
    cout << "修改后的数组：";
    for (int i = 1; i <= n; i++) {
        new_a[i] = new_a[i-1] + diff[i];   // 累加差分得到新值
        cout << new_a[i] << " ";
    }
    cout << endl;

    return 0;
}

运行示例（输入输出）：

请输入数组大小：10
请输入10个整数：70 80 90 85 75 60 95 88 92 78
请输入操作次数：3
第1次操作（l r x）：1 5 3
第2次操作（l r x）：4 8 -2
第3次操作（l r x）：2 9 5
修改后的数组：73 88 98 91 81 63 98 91 97 78

手动验算：第1步后 [73, 83, 93, 88, 78, 60, 95, 88, 92, 78]；第2步后 [73, 83, 93, 86, 76, 58, 93, 86, 92, 78]；第3步后 [73, 88, 98, 91, 81, 63, 98, 91, 97, 78]，结果正确。

新手容易犯的错误

数组越界：当区间右端点 r = n 时，diff[r+1] 即 diff[n+1] 必须存在。所以差分数组至少要多申请一个元素（比如 diff[105] 如果 n<=100）。
忘记初始化 diff[0]：虽然我们一般不用 diff[0]，但在求前缀和时 new_a[0] 必须为0。另外，构建差分时如果对 diff[1] 的赋值使用 a[1] - a[0]，要保证 a[0]=0，或者直接用 a[1]。
多次操作后忘记处理 diff[r+1] 的叠加：每次操作都要在 diff[l] 和 diff[r+1] 上累加，而不是覆盖。因为多个操作的效果是叠加的。
下标从0开始混淆：很多入门教材习惯用0下标，但差分通常用1下标更方便（边界处理简单）。如果在0下标数组上使用，公式要调整为：diff[l] += x; diff[r+1] -= x; 其中 r+1 可能等于数组长度（不能越界）。
把差分和前缀和混用：差分用于区间修改，前缀和用于区间求和（比如求原数组第l到r项的和）。两者结合使用时要分清用途。

什么是差分？——批量修改数据的快捷方法

什么是差分？——批量修改数据的快捷方法

为什么要用差分？

什么是差分？——差分数组的定义

区间修改的原理——只需两步操作

用积木例子理解

用生活例子理解——发零花钱

差分与前缀和的关系

多次区间修改的例子

完整可运行的示例代码

新手容易犯的错误

相关指引

例题精讲