前缀和

前缀和

前缀和就是记录第一个元素到后面每个元素的和

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int a[n+10],b[n+10];
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<b[r]-b[l]+a[l]<<endl;
    }
    return 0;
}

子矩阵的和

把一维数组换成二维数组

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    int a[n+10][m+10],b[n+10][m+10];
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1]<<endl;
    }
    return 0;
}

差分

差分

差分对于一维数组来说就是记录从第一个元素到后面每一个元素的和，比如a[1]记录第一个元素的值，a[2]记录第一个和第二个元素的和，以此类推，最后求的是区间值，比如第2个元素到第4个元素的值就可以用a[4]-a[1]表示（包括第二个元素）

#include<bits/stdc++.h>
using namespace std;

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

差分矩阵

差分矩阵就是把一维数组换成二维数组，每个元素记录从左上角到这个位置的和

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n,m,q;
    cin>>n>>m>>q;
    int a[n+10][m+10],b[n+10][m+10];
    memset(b,0,sizeof(b));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        b[x1][y1]+=c;
        b[x2+1][y1]-=c;
        b[x1][y2+1]-=c;
        b[x2+1][y2+1]+=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];
            cout<<a[i][j]+b[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}