（基础）--- 前缀和、差分

一维前缀和

顾名思义：前缀和就是数组前n项和

注意：数组下标从1开始防止越界

1、预处理前缀和数组
2、用公式求区间和

//求前缀和
s[i] = s[i-1]+a[i];
//求数组下标在l，r之间的元素之和
s[r]-s[l-1]

二维前缀和

用二维矩阵来计算

// 求s[i,j] 表示矩阵大小为行i，列j的元素之和
s[i][j] = s[i-1][j]+s[i][j-1] - s[i-1][j-1] + a[i][j];
// 求s[x1,y1]到s[x2,y2]之间的元素之和
s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1];

#include<iostream>

using namespace std;
const int N = 1010;

int n,m,q;
int a[N][N],s[N][N];

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

一维差分

给定a[1],a[2],...a[n]构造差分数组b[N],使得a[i] = b[1]+b[2]+...+b[i]
b[i]=a[i]-a[i-1];
核心操作：将a[L~R]全部加上C，等价于：b[L]+=C,b[R+1] -= C;
1、a[1~L-1]无影响
2、a[L~R]加上了C
3、a[R+1~N]无影响

实现差分

有的操作利用了前缀和，差分是前缀和的逆运算

// b[N] 初始全为0
void insert(int l,int r,int c){
    b[l]+=c;
    b[r+1]-=c;
}
//利用前缀和来还原数组数据
for(int i = 1; i <= n; i ++ ) a[i] = a[i-1] + b[i];


//整体操作:计算差分数组b[N]，将序列中[l, r]之间的每个数加上c，还原原数组
#include<iostream>

using namespace std;
const int N = 1e5+10;

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(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin>>a[i];
    
    for(int i = 1; i <= n; i ++ ) insert(i,i,a[i]);
    
    while(m -- ){
    	int l,r,c;cin>>l>>r>>c;
    	insert(l,r,c);
	}
    
    for(int i = 1; i <= n; i ++ ) a[i] = a[i-1] + b[i];
    
    for(int i = 1; i <= n; i ++) cout<<a[i]<<" ";
}

二维差分

给定原矩阵a[i,j]，构造差分矩阵b[i,j],使得a[][]是b[][]的二维前缀和

二维差分核心操作

给以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中的所有数a[i,j],加上C。

//对于差分数组的影响：

b[x1,y1] += C;
b[x1,y2+1] -=C;
b[x2+1,y1] -= C;
b[x2+1,y2+1] +=C;

#include<iostream>

using namespace std;
const int N = 1e3+10;

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

void insert(int x1,int y1,int x2,int y2,int c){
	b[x1][y1]+=c;
	b[x1][y2+1]-=c;
	b[x2+1][y1]-=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];
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; 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 ++ ){
			a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
		}
	}
	
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++ ){
			cout<<a[i][j]<<" ";
		}
		puts("");
	}	
}