一维差分

一维差分主要解决的是需要在一维区间内进行大量的加减常数

思考步骤

给定一个数组s，当需要在一个区间内进行加减常数时，暴力循环明显时O(n)的时间复杂度。 如果我们构建一个数组a，使得原数组s是a的前缀和数组，那么a也就是s的差分数组 我们可以发现，当需要s在[l,r]加c时，我们只需要对于a[l]+c,a[r+1]-c，即可在O(1)内完成操作，最后再求一下前缀和就是答案

公式

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

同时，差分数组的初始化也可以使用这个公式，只需传入(i,i,s[i])即可

实现

具体实现和讲解

#include <iostream>

using namespace std;

const int N=1e6+10;

int a[N],s[N];


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

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) 
    {
        cin>>s[i];
        insert(i,i,s[i]);
        
    }

    for(int i=1;i<=m;i++)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        
        a[i]+=a[i-1];
        cout<<a[i]<<" ";
    }
    return 0;
}

二维差分

和一维差分相同，不过提升到了二维

公式

void insert(int x1,int y1,int x2,int y2,int c){
    a[x1][y1]+=c;
    a[x1][y2+1]-=c;
    a[x2+1][y1]-=c;
    a[x2+1][y2+1]+=c;
}

实现

具体题目和讲解

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N][N],s[N][N];
void insert(int x1,int y1,int x2,int y2,int c){
    a[x1][y1]+=c;
    a[x1][y2+1]-=c;
    a[x2+1][y1]-=c;
    a[x2+1][y2+1]+=c;
}
int main(){
    int m,n,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&s[i][j]);
            insert(i,j,i,j,s[i][j]);
        }
    }
    while(q--){
        int x1,x2,y1,y2,c;
        scanf("%d%d%d%d%d",&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++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            printf("%d ",s[i][j]);
        }
        cout<<endl;
    }
}