差分

定义

差分与前缀和是互逆的运算，假设差分数组为b,原数组为a
即有：
b[0]=a[1]-a[0];
b[1]=a[2]-a[1];
……
b[s-1]=a[s]-a[s-1];
b[s]=a[s+1]-a[s];
……
b[t]=a[t+1]-a[t];
……
b[n]=a[n+1]-a[n];
两个数组能表示的信息时一样多的，这也就是说知道一个可以推出另一个。

应用

当在原数组的某个区间的每个数都加上时，可以利用差分数组将O(n)级别的操作转为O(1)
观察两个数组，假设在a[s]~a[t]的每个数都加上c，也就等同于b[s]+c,b[t+1]-c
于是只改变区间端点的两个值在直观理解上就可以改变整个区间的值。

如何构造差分数组b

假设最初两个数组都是初始化为0,我们将a初始化的同时得到b,利用计算差分数组的方法来初始化，下面是操作方法：

insert(int l,int r,int c){
    b[l]+=c;//这样做之后a[l]及其之后的数都会加上c
    b[r+1]-=c;//由于要固定在区间内，将多加的c减掉
}
for(int i=1;i<=n;i++) insert(i,i,a[i]);

这样就得到了差分数组。

例子

https://www.acwing.com/activity/content/problem/content/831/
代码：

#include<iostream>
using namespace std;
const int N=100010;

int n,m;
int a[N],b[N];

void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}

int main(){
    int l,r,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
        insert(i,i,a[i]);
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&l,&r,&c);
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++){
        b[i]+=b[i-1];
        printf("%d ",b[i]);
    }
    cout<<endl;
    return 0;
}