一、差分算法的实际应用#

在处理将一个数组中某个区间内的所有值均加上或减去一个常数时，

为了进一步的简化程序计算量，我们可以考虑差分算法的应用。

问题：

若给定区间[l , r]，并将数组a中的[ l, r]区间中的每一个数都加上c

即 a[l]+c , a[l + 1]+c , a[l + 2]+c ……a[r]+c

传统模拟暴力做法是使用for循环，从l循环到r，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。

通过差分算法，我们可以将O(m*n)的时间复杂度简化至O(n)，显著简化计算。

二、差分数组的定义#

我们可以将差分看作为：数组中每个元素与其前一个元素的差。

例：

首先给定一个原数组a：a[1], a[2], a[3]……a[n]

然后我们构造一个数组b ： b[1] ,b[2] , b[3]……b[i]

使得 a[i] = b[1]+b[2 ]+ b[3] +……+ b[i]

我们把 数组b 叫做 数组a 的差分数组。

换句话说，每一个a[i]都是数组b中从首项开始到第i项的一段区间和。

三、差分数组的生成#

由差分数组的定义易得：

a[0 ]= 0

b[1] = a[1] - a[0]

b[2] = a[2] - a[1]

b[3] =a [3] - a[2]

……

b[n] = a[n] - a[n-1]

四、差分数组的应用#

始终要记得，数组a是数组b的前缀和数组，比如对数组b的b[i]的修改，会影响到数组a中从a[i]及往后的每一个数。

首先让差分数组b中的 b[l]+c ，

使得，数组a变成 a[l]+c ,a[l + 1]+c……a[n]+c

然后我们新引入一个b[r + 1] - c，

使得，数组a变成 a[r + 1] - c,a[r + 2] - c……a[n]-c

新引入的 b[l] + c 使得数组a中 a[l]及以后的数都加上了c(红色部分)，

但我们只要求l到r区间加上c, 因此还需要执行 b[r+1] - c,让数组a中a[r+1]及往后的区间再减去c(绿色部分)，

这样对于a[r] 以后区间的数相当于没有发生改变。

因此我们不难看出：给数组a中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。

五、方法#

对数组a区间[l,r]同时加上c的操作可转化为：

for(int i=1;i<=n;i++)//输入源数组a，n为数组a长度
{
	cin>>a[i];
	b[i]=a[i]-a[i-1];
}

int j,k,c;
while(m--)//生成差分数组b，m次操作
{
	cin>>j>>k>>c;
	b[j]+=c;
	b[k+1]-=c;
}

再对数组b求前缀和即可得到原数组a：

for(int i=1;i<=n;i++)//根据数组b前缀和，还原源数组a
{
    a[i]=b[i]+a[i-1];
    cout<<a[i]<<' ';
}

六、例题（摘选自AcWing 797）#

AC示例：

#include <iostream>
using namespace std;
const int N=1e5+1;
int a[N],b[N];

int main()
{
    int n,m;
    cin>>n>>m;

    for(int i=1;i<=n;i++)//输入源数组a
    {
        cin>>a[i];
        b[i]=a[i]-a[i-1];
    }
    
    int j,k,c;
    while(m--)//生成差分数组b
    {
        cin>>j>>k>>c;
        b[j]+=c;
        b[k+1]-=c;
    }
    
    for(int i=1;i<=n;i++)//根据数组b前缀和，还原源数组a
    {
        a[i]=b[i]+a[i-1];
        cout<<a[i]<<' ';
    }
    
    cout<<endl;
    return 0;
}