对于数列a1-an构建数列b1-bn
满足以下性质：
ai=b1+b2+...+bi

即对于b数列,a数列是它的前缀和 而对于a数列b就是它的差分。

差分有什么用？

假设需要对一个数列a的区间[l,r]频繁的做加c的操作

根据定义数列b的l位置+c，由于数列a是他的前缀和。 即a数列l后面的数都会加c
然后我们在b的r+1位置-c 就实现了区间[l,r]+c的操作！
https://www.acwing.com/problem/content/799/

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
const int N=1e5+5;
int n,m;
int a[N],b[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i]-a[i-1];//构建差分
    }
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        b[l]+=c;
        b[r+1]-=c;
    }
    //通过求b数列的前缀和来获得a数列
    for(int i=1;i<=n;i++){
        a[i]=a[i-1]+b[i];
        cout<<a[i]<<" ";
    }
  return 0;
}
//  freopen("testdata.in", "r", stdin);

优化简单版
吧a数列和b数列最初状态都看成0
如果a[1]=1 就看成对区间[1,1]+1
那么我们甚至不用构建差分数列，实现插入函数即可

#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()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);

    while (m -- )
    {
        int l, r, c;
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    }

    for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];

    for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);

    return 0;
}

二维差分

https://www.acwing.com/problem/content/description/800/
原理一样 实现复杂了一点点

#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
using namespace std;
int n,m,q;
int a[1005][1005];
int b[1005][1005];
void insert(int x1,int y1,int x2,int y2,int c){
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",b[i][j]);
        }
        printf("\n");
    }

  return 0;
}
//  freopen("testdata.in", "r", stdin);

模板 差分

原文：https://www.cnblogs.com/OfflineBoy/p/14588658.html