差分算法：快速更新区间

对于刚接触算法的同学来说，面对“多次区间修改+最终查询”类问题（比如给数组的某段区间都加5、给某段区间的值都减3），第一反应往往是用循环遍历区间逐个修改——但如果区间范围很大（比如1~100000）、修改次数很多（比如10000次），这种暴力做法会超时。

而差分算法用两个简单的数组操作，就能把“m次区间修改”的时间复杂度从O(nm)优化到O(m)，每次区间修改只需要O(1)，无需遍历数组。

一、差分算法的核心思想：用“差值”代替“整体修改”

我们先从最基础的数组说起：
假设有一个原始数组 arr[1...n]（为了方便边界处理，下标从1开始），比如 arr = [0, 2, 5, 4, 9]（arr[0]仅作边界，无意义）。

1. 什么是差分数组？

我们定义一个差分数组 diff，它的长度和原始数组一致，满足：

diff[1] = arr[1]（差分数组第一个元素等于原数组第一个元素）；
对于 i > 1，diff[i] = arr[i] - arr[i-1]（差分数组第i个元素 = 原数组第i个元素 - 原数组第i-1个元素）。

举个例子：
原数组 arr = [0, 2, 5, 4, 9]（下标1~4），对应的差分数组：

diff[1] = 2；
diff[2] = 5 - 2 = 3；
diff[3] = 4 - 5 = -1；
diff[4] = 9 - 4 = 5；
最终 diff = [0, 2, 3, -1, 5]。

2. 差分数组的“反向操作”：还原原数组

差分数组的核心价值在于：对差分数组做“前缀和”，就能还原出原始数组。
还是上面的例子：

前缀和第一步：2 → 对应原数组arr[1]=2；
前缀和第二步：2+3=5 → 对应原数组arr[2]=5；
前缀和第三步：5+(-1)=4 → 对应原数组arr[3]=4；
前缀和第四步：4+5=9 → 对应原数组arr[4]=9；
这是差分算法的基础，一定要记住：差分数组求前缀和得到原始数组。

3. 区间修改的核心技巧

这是差分算法最关键的部分：
如果我们想给原数组的区间 [l, r] 内的所有元素都加上一个数 k，不需要遍历区间修改每个元素，只需对差分数组做两个操作：

diff[l] += k（给区间起点的差值加k）；
若 r+1 ≤ n，则 diff[r+1] -= k（给区间终点的下一个位置的差值减k）。

举个例子：
原数组 arr = [0, 2, 5, 4, 9]，差分数组 diff = [0, 2, 3, -1, 5]，想给区间 [2, 3] 加2：

第一步：diff[2] += 2 → diff[2] = 3+2=5；
第二步：diff[4] -= 2 → diff[4] = 5-2=3；
修改后差分数组 diff = [0, 2, 5, -1, 3]。

对修改后的差分数组做前缀和还原原数组：

2 → arr[1]=2；
2+5=7 → arr[2]=7（原5+2=7）；
7+(-1)=6 → arr[3]=6（原4+2=6）；
6+3=9 → arr[4]=9（无变化）；
完全符合“区间[2,3]加2”的需求！

核心逻辑解释

为什么仅修改两个位置就能实现区间更新？

diff[l] += k：意味着从l位置开始，原数组的所有元素都会“继承”这个k（因为前缀和会一直累加）；
diff[r+1] -= k：意味着从r+1位置开始，抵消这个k的影响，保证只有[l, r]区间内的元素被修改。
相当于用两个“标记点”，精准控制修改的区间范围，无需逐个操作。

二、差分算法的固定步骤

无论面对什么区间修改问题，差分算法的步骤都是固定的4步，记牢就能直接用：

步骤1：初始化原数组和差分数组

定义原始数组 arr（根据题目输入初始化，下标建议从1开始）；

构建差分数组 diff：

// 假设arr下标从1到n
diff[1] = arr[1];
for (int i = 2; i <= n; i++) {
    diff[i] = arr[i] - arr[i-1];
}

特殊情况：如果原数组初始全为0（比如“校门外的树”这类初始无值的问题），差分数组可直接初始化为全0。

步骤2：处理所有区间修改操作

对每个“给区间[l, r]加k”的操作，执行：

diff[l] += k;
if (r + 1 <= n) {
    diff[r+1] -= k;
}

（如果是“减k”，只需把k换成-k即可）

步骤3：对差分数组做前缀和，还原修改后的原数组

arr[1] = diff[1]; // 第一个元素直接等于差分数组的第一个元素
for (int i = 2; i <= n; i++) {
    arr[i] = arr[i-1] + diff[i];
}

三、经典应用：校门外的树（进阶版）

这是差分算法最经典的入门题，我们用“高效版”解法替代之前的暴力循环：

题目原型

校门外有一条长度为L的道路，0~L位置共有L+1棵树（初始都存在）。有M次操作，每次操作要么砍掉[start, end]区间的树，要么补种[start, end]区间的树。求最终剩余多少棵树。

解题分析（差分版）

步骤1：原数组 tree[0...L] 初始全为1（1表示树存在），构建差分数组 diff[0...L+1]（多开一个位置避免r+1越界）：
- diff[0] = 1；
- 对于i>0，diff[i] = tree[i] - tree[i-1] = 1-1=0，所以初始差分数组全为0（除了diff[0]=1）。
步骤2：处理每次操作：
- 砍掉[start, end]：相当于给区间加-1 → diff[start] -=1，diff[end+1] +=1；
- 补种[start, end]：相当于给区间加1 → diff[start] +=1，diff[end+1] -=1。
步骤3：对diff做前缀和，还原tree数组；
步骤4：统计tree数组中值为1的元素个数（树存在）。

核心代码（C++）

#include <iostream>
using namespace std;

const int MAX_L = 1001; // 道路最大长度1000，多开1个位置防越界
int diff[MAX_L + 2]; // 差分数组，长度1003
int tree[MAX_L + 1]; // 原数组，记录树的状态

int main() {
    int L, M;
    cin >> L >> M;
    
    // 步骤1：初始化差分数组（原数组全1，差分数组除diff[0]=1外全0）
    diff[0] = 1;
    for (int i = 1; i <= L+1; i++) {
        diff[i] = 0;
    }
    
    // 步骤2：处理M次操作
    for (int i = 0; i < M; i++) {
        int start, end, op;
        cin >> op >> start >> end; // op=1砍树，op=2补种
        int k = (op == 1) ? -1 : 1;
        
        diff[start] += k;
        if (end + 1 <= L) {
            diff[end + 1] -= k;
        }
    }
    
    // 步骤3：前缀和还原原数组
    tree[0] = diff[0];
    for (int i = 1; i <= L; i++) {
        tree[i] = tree[i-1] + diff[i];
    }
    
    // 步骤4：统计剩余树的数量
    int res = 0;
    for (int i = 0; i <= L; i++) {
        if (tree[i] == 1) { // 值为1表示树存在
            res++;
        }
    }
    cout << "剩余树的数量：" << res << endl;
    return 0;
}

四、注意事项

下标越界问题：
- 差分数组一定要多开1~2个位置（比如原数组长度n，差分数组长度n+2），避免r+1超过数组范围；
- 建议原数组下标从1开始，减少边界判断的复杂度。
初始值错误：
- 如果原数组初始全为0，差分数组可直接初始化为0；
- 如果原数组有初始值，必须严格按diff[i] = arr[i] - arr[i-1]构建，不能偷懒。

五、差分与前缀和的关系

差分和前缀和是互逆操作，可以理解为“加减法”的关系：

操作	核心作用
前缀和	快速查询区间和
差分	快速修改区间值

想快速查询区间和 → 用前缀和；
想快速修改区间值 → 用差分；
差分的最终还原依赖前缀和，前缀和的逆运算就是差分。

这两个算法经常搭配使用，比如“多次区间修改+最终查询区间和”的问题，解法就是：差分处理修改 → 前缀和还原数组 → 前缀和查询区间和。

六、总结：

学习差分算法的关键是理解“用两个标记点控制区间修改”的思想。感觉理解困难的同学建议手动推导差分数组的变化和还原过程，当你能手动算出每一步的结果时，就真正掌握了这个算法。

后续学习二维差分、树状数组、线段树等进阶区间算法时，差分的思想依然是核心。

差分