一维差分算法篇：高效处理区间加减

那么在正式介绍我们的一维差分的原理前，我们先来看一下一维差分所应用的一个场景，那么假设我们现在有一个区间为[L,R]的一个数组，那么我要在这个数组中的某个子区间比如[i,m] (L<=i<=m<=R)进行一个加k值或者减去k值的一个操作，那么我们常规的暴力方法就是我们直接遍历一遍该数组的子区间每个位置加k或者每个位置减k，那么一旦该操作多了，那么对数组的遍历就过于频繁，那么我们能不能用一个较小的代价来完成这每个区间的加k值或者减k值的所有操作而不是每次都去遍历一遍数组呢，那么我们的一维差分就能做到这一点。

1.一维差分原理

那么我们现在有一个区间为[L,R]的一个数组，那么我们要在其中的任意的子区间加k或者减k，那么这里我们目标是想得到我们这个数组从原始状态经过该操作后也就是在任意子区间加减k值后的一个最终状态，那么我们对这个数组的任意子区间的加减操作我们可以理解为我们要在数组原状态下所叠加的状态，那么如果我们能够知道我们数组各种叠加状态后的综合得到的一个最终的叠加状态，那么我们数组在此基础上只需要叠加一个综合的叠加状态那么就可以得到最终状态了。

这里我们还是举一个例子来解释一下我刚才的一个观点，那么假设我们有长度为10的一个原数组[1,2,3,4,5,6,7,8,9,10],那么这里假设我们对这个[0,9]区间的数组中的[0,4]区域处整体减去3，在[0,2]区域处整体加2，最后在[3,5]区域处整体加1，那么我们要知道在这三个操作下我们数组最终的状态的各个位置的值是怎样的

那么我们这里可以把我们数组最开始的形态：[1,2,3,4,5,6,7,8,9]视作初始状态，而我们这三次操作比如在[0,4]区域处整体减去3，视作我们要叠加的状态，那么这里我们如果要得到我们的目标数组，我们肯定是分别叠加三次要叠加的状态，比如在[0,4]减3，然后再[0,2]区域加二，最后在[3,5]区域加1，最终得到我们数组的最终状态也就是[0,1,2,2,3,5,6,7,8,9],那么现在我们希望就是只用叠加一次状态就得到我们的最终状态，那么这里我们只用叠加一次，那么也就意味着我们要知道这三次叠加状态的一个综合效果。

那么这里得到这里所谓的综合得到的叠加状态，就是通过建立一个差分数组diff，该数组的下标就对应我们原始数组的相应位置，那么其中的每个位置的值则表示我们原始数组中对应位置最终该叠加的一个状态也就是[-1,-1,-1,-2,-2,0,0,0,0,0]，那么我们原始数组每个位置加上对应的值就能够得到我们最终状态也就是[0,1,2,2,3,5,6,7,8,9]，也就只需要遍历一遍数组即可。

所以现在的疑问就转变为了如何加载这个差分数组diff，那么这里我们假设我们要在区间[L,R]中的子区间[i,m]处加v，那么这里我们需要一个与我们原始数组长度对应的一个差分数组，然后将其初始化每个位置的大小都为0，然后我们这里只需要在下标为i位置处加v，然后再m+1处加-v，然后对该差分数组加载对应的一份前缀和数组，那么我们就可以把前缀和数组中区间[i,m]的整体的值给全部刷成v，那么我们对于区间[i,m]的每个位置上的数要叠加的状态就是该区间的每个数加v，那么我们通过这两步就能得到区间[i,m]的叠加状态。

看到这里你想必一定有两个疑问，第一问是想问我为什么要在i位置处加v，在m+1位置处要减去v？第二问则是为什么加工一遍前缀和就能够得到该操作下的叠加状态？

这里我们知道我们的叠加状态就是对整个区间统一进行加或者减去定值k，那么这里我们要得到该状态所对应的差分数组的话，那么差分数组中对应[i,m]的值一定全部是k或者-k，那么这里我们如何将差分数组中的[i,m]全部设置为k或者-k呢，当然肯定不是通过遍历，而这时候前缀和派上用场了，因为我们前缀和的计算公式是sum[i]=sum[i-1]+arr[i]，那么我们发现如果我们在i位置处加一个v，那么根据前缀和的公式：sum[i]+v=sum[i-1]+(arr[i]+v),那么此时i位置加v之前对于第i+1位置的前缀和是：sum[i+1]=sum[i]+arr[i+1],但是我们由于i位置加了一个v，那么sum[i]此时的值是sum[i]+v,那么对于sum[i+1]来说，由于sum[i+1]=sum[i]+v+arr[i+1],而现在sum[i]的值变成了sum[i]+v，所以sum[i+1]的值就变成了sum[i+1]+v,那么我们可以依次类推：

那么这里我其实就可以观察到我们在i位置处加v，然后加工一遍前缀和，我们包括i位置在内以及之后的每一个前缀和都会加v，那么这个加v的效果会持续到包括i位置在内的右侧的所有区间，那么根据我们上面的式子，由于我们差分数组的每个数初始化为0，那么也就意味着我们在sum[i]的前缀和是0，那么我们如果不加v的话，那么我们这个差分数组加工得到的前缀和数组的每个位置都是0,但是由于我们这里在i位置加了v，那么我们知道我们在包括i位置之后的右侧区间全部会刷成v，但是我们只要[i,m]处刷成v，那么我们得到m位置之后抵消这个加v的效果，那么我们就在m+1位置从设置-v，那么我们m+1以及右侧的位置都会有一个加-v的效果，那么与前面的抵消了，所以这就是为什么我们在i位置处设置v,m+1位置处设置-v，然后加工一遍前缀和的原因。

那么我们如果在[i,m]区间处减去v的话，只要你看懂我们上面的原理，那么就不用我再去讲解赘述了，所以我们对于多次这样的操作，比如在某个区间[i,m]加v或者减去v，那么我们就根据上文讲的原理，在对应位置处i位置加或者减去v，然后再相应的m+1位置处减或者加v，然后加工一遍前缀和，就能得到这所有操作综合的叠加状态了

那么这里其实代码模版就很简单，就是一个差分数组和对应加工的前缀和数组，只不过这里在实现的时候注意边界问题，因为我们如果在比如[i,R]区间上加v或者减v，R是我们这个数组的右边界，那么我们的差分数组如果跟原数组长度一样的话，那么根据刚才的原理，我们会在R+1位置处减v或者加v，那么为了不越界的话，我们会加上一些条件判断，但是如果你不想讨论边界的话，你的差分数组的长度就可以比原数组大一个单位，也就是原数组的长度是n，那么你的差分数组1长度就是n+1，然后按照刚才的思路去在相应的位置设置值，最后只需要加工一遍前缀和即可。

公式：

在[i,m]统一加v：diff[i]+v diff[m+1]-v

在[i.m]统一减v：diff[i]-v diff[m+1]+v

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr(10) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> diff(arr.size() + 1, 0); // 差分数组长度应为原数组长度+1

    // 假设要在[0,3]区间加3，在[2,4]区间减2
    diff[0] += 3;
    diff[4] -= 3; // 注意这里是4，因为区间是[0,3]，所以结束位置+1
    diff[2] -= 2;
    diff[5] += 2; // 同样，区间是[2,4]，所以结束位置+1

    vector<int> diffsum(arr.size()+1, 0); 

    for (int i = 1; i < arr.size(); i++) {
        diffsum[i] = diffsum[i - 1] + diff[i-1];
    }
    return 0；
}

那么很多人看完这个一维差分，感觉差分不是很高效，我们加载一遍前缀和意味着要遍历一遍数组，那么复杂度是o(N),那么如果说我们只是对区间[L,R]的数组中某个子区间统一的加或减去v，那么根绝还不如我直接遍历这个子区间高效，但是我们差分数组在面对这样的场景，比如你这里要对数组的子区间进行100次甚至1000多次的加v或者减v操作，如果这个数组还特别长的话，那么此时长分就只需要遍历一遍数组即可，所以此时差分的优秀就体现出了

2.等差数列差分

那么我们这里有一个特殊的差分也就是等差数列差分，那么我们这里假设要在区间[i,m]中叠加的状态是一个等差数列，那么该等差数列首项是s，公差是d，那么i位置是s，往后依次是s+d，s+2d，所以最终的叠加状态：

[s,s+d,s+2d,s+3d,…,s+(i-m)*d]

那么这里我们要得到该叠加状态其实我们加载一遍前缀和是不够的，因为一边前缀和只能将区间刷成一个统一的值比如s比如d，那么这里一遍不够，那么也就意味着我们要加载两边前缀和，那么这里我们要得到我们加载两边前缀和数组的初始差分数组的形态，那么我们就采取逆推

我们这里先推最终叠加状态的上一级状态也就是中间状态，那么我们这里[i.m]每个位置都有首项s，那么这里我们的i位置就得加上s，然后m+1位置处减去s,那么这里由于我们这里i+1到n处的d是依次递增的，那么我们这里i+1到m处肯定都有一个d值，这样加载前缀和，前面的加d的效果到后面一个位置，那么在加上后面本身有一个d，那么该位置就得到2d，那么在往后传递，就能做到递增，但是要在m之后的区间抵消，那么我们就得在m+1位置处减去(i-m)*d

那么我们要得到中间状态，也就是[s,d,d,d,d,d,d,…，-（s+(i-m)*d）]那么我们则需要在l位置设置为s，l+1位置处设置为d-s，然后m+1位置处设置为-(s+(i-m))*d),然后我们加工两遍前缀和数组即可

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 10; // 数组长度
    int i = 2;  // 区间起始位置
    int m = 5;  // 区间结束位置
    int s = 3;  // 等差数列首项
    int d = 2;  // 等差数列公差

    vector<int> arr(n, 0); // 原始数组
    vector<int> diff(n + 1, 0); // 差分数组

    // 初始化差分数组
    diff[i] += s;
    if (i + 1 <= m) {
        diff[i + 1] += -s + d;
    }
    if (m + 1 < n) {
        diff[m + 1] -= s + (m - i) * d;
    }

    // 第一次前缀和，得到中间状态
    vector<int> mid(n, 0);
    diff[0]=0
    for (int j = 0; j < n; j++) {
        mid[j] = mid[j] + diff[j];
    }

    // 第二次前缀和，得到最终状态
    vector<int> result(n, 0);
    result[0] = mid[0];
    for (int j = 1; j < n; j++) {
        result[j] = result[j - 1] + mid[j];
    }
    return 0;
}

3.结语

那么我们差分是我们处理区间加减操作的一个非常常用高效的一个算法，那么这里的差分我们是一维差分，那么既然都说了是一维差分，那么必然就有二维差分，那么我们了解了一维差分的原理之后，那么其实二维差分我们也大概知道它的用途，那么就是针对于二维数组某个区域的统一的加减问题，那么我会在之后的文章中会讲解我们的二维差分以及二维差分需要用到的二维前缀和，那么希望本文能够让你有所收获，我会持续更新，也希望你多多关注与支持，你的支持就是我最大的动力！