前缀和与差分

前缀和与差分

前缀和

作用:快速求出数值中某段位置的数值和,降低时间复杂度

一维前缀和

//基本思想
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]

//实现案例
/*
输入一个长度为n的整数序列。
接下来再输入m个询问，每个询问输入一对l,r。
对于每个询问，输出原序列中从第l个数到第r个数的和。
*/
#include<iostream>
using namespace std;

const int N = 100010;
int n,m;
int q[N],s[N];
int l,r;

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i<=n;i++){
    scanf("%d",&q[i]);
    s[i]=s[i-1]+q[i];
    }
    
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%d\n",s[r]-s[l-1]);
    }
    return 0;
}

二维前缀和

//基本思想,涉及到容斥原理
S[i, j] = 第i行j列格子左上部分所有元素的和
(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

//实例,子矩阵的和
#include<iostream>
using namespace std;

const int N = 1010;
int q[N][N],s[N][N];
int n,m,num;

int main(){
    scanf("%d%d%d",&n,&m,&num);
    for(int i = 1;i<=n;i++)
    for(int j = 1 ;j<=m; j++){
        scanf("%d",&q[i][j]);
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+q[i][j];
    }
    
    while(num--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
    }
    return 0;
}

差分

可以看成前缀和的逆运算,对原数组某一段区间加上固定数值,降低时间复杂度

一维差分运算

//给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c

//向整数序列变动区间位置频繁进行相加相减操作
#include<iostream>
using namespace std;

const int N =100010; 
int len,num;
int q[N],t[N];

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

int main(){
    scanf("%d%d",&len,&num);
    for(int i = 1;i<=len;i++){
        scanf("%d",&q[i]);
        insert(i,i,q[i]);
    }
    int a,b,c;
    while(num--){
        scanf("%d%d%d",&a,&b,&c);
        insert(a,b,c);
    }
    for(int i = 1;i<=len;i++){
        t[i]+=t[i-1];
        printf("%d ",t[i]);
    }
    return 0;
}

二维差分运算

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c

//差分矩阵
#include <iostream>
using namespace std;

const int N = 1010;
int q[N][N],t[N][N];
int n,m,num;

void insert2d(int x1,int y1,int x2,int y2,int num){
    t[x1][y1]+=num;
    t[x2+1][y1]-=num;
    t[x1][y2+1]-=num;
    t[x2+1][y2+1]+=num;
}

int main(){
    scanf("%d%d%d",&n,&m,&num);
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++){
            scanf("%d",&q[i][j]);
            insert2d(i,j,i,j,q[i][j]);
        }
        
    while(num--){
        int x1, y1, x2, y2,add;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&add);
        insert2d(x1,y1,x2,y2,add);
    }
    
     for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            t[i][j]+=t[i-1][j]+t[i][j-1]-t[i-1][j-1];
            printf("%d ",t[i][j]);
        }
        printf("\n");
     }
    return 0;
}