一维前缀和数组

n个元素，m次询问
将时间复杂度简化到O（1）
sum[L,R]=sum[R]-sum[L-1] L>0
sum[L,R]=sum[R] L=0
O(n*j)
一维前缀和

#incldue<iostream>
using namespace std;

#define get_sum(L,R)(L?sum[R]-sum[L-1]:sum[R])
int get_sum(int L,int R){
	if(L!=0){
		return sum[R]-sum[L-1];
	}
	else return sum[R];
}
int main(){
const int n=5;
	int arr[n]={1,3,7,5,2};//原数组
	int sum[n];//前缀和数组
	sum[0]=arr[0];
	for(int i=1;i<n;i++)
	{
		sum[i]=sum[i-1]+arr[i];
	}
	for(int i=0;i<n;i++)
	cout<<sum[i]<<"  ";//输出一维前缀和数组
	
	cout<<get_sum(2,4)<<endl;
	cout<<get_sum(0,3)<<endl;
	cout<<get_sum(3,4)<<endl;
return 0;
}
//1 3  7  5  2
//1 4 11 16 18

一维差分

差分数组 和 前缀和数组 可以得到 原数组
O（n+m）

arr（原数组）	1	3	7	5	2
d(差分)	1	2	4	-2	-3
sum（d）（前缀和）	1	3	7	5	2

差分标记：[L,R]+ V <=>d[L]+V ,d[R+1]-V

把标记后的 差分数组 进行 前缀和 操作
适用于多次操作单次（少次）询问

#include<iostream>
using namespace std;
int d[6]={0};
void add(int l,int r int v){
	d[l]+=v;
	d[r+1]-=v;
}
int  main(){
	int arr [5]={1,3,7,5,2};
	add(2,4,5);
	add(1,3,2);
	add(0,2,-3);
	for(int i=1;i<5;i++){
		d[i]+=d[i-1];
	}
	for(int i=0;i<5;i++){
		arr[i]+=d[i];
		cout<<arr[i]<<" ";
	}
	memset(d,0,sizeof(0));//如果查询多次可以初始化
return 0;
}

二维前缀和

定义：sum[i][j]是从[0,0]到[i,j]的和
O(1)求矩阵和

sum[x1,y1][x2,y2]= sum[x2][y2]  -sum[x2][y1-1] -  sum[x1-1][y2]  + sum[x1-1][y1-1]

sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]

注：当出现i-1，j-1需要考虑数组越界
所以

当i=0，且j=0时 sum[0][0] =g[0][0]

当i=0，sum[0][i]=sum[0][i-1]+g[0][i]
sum{0,y1}{0,y2}=sum[0][y2]-sum[0][y1-1]

当j=0
sum[i][0]=sum[i-1][0]+g[i][0]
sum{x1,0}{x2,0}=sum[x2][0]-sum[x1-1][0]

或者在创建二维数组时，将数据从（1，1）开始写起，也就是同时将（0，i）为0，（j，0）为0，但是有时不允许

#include<iostream>
using namespace std;
const int n=3，m=4;
int g[n][m]={{1,5,6,8},
			 {9,6,7,3},
			 {5,3,2,4} }
int sum[n][m];
void pre_sum(){
	sum[0][0]=g[0][0];//第一个
	for(int i=1;i<n;i++)sum[i][0]=sum[i-1][0]+g[i][0];//第一列
	for(int j=1;j<m;j++)sum[0][j]=sum[0][j-1]+g[0][j];//第一行
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
		sum[i][j]=g[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];//g为右下角
		}
	}
}
int get_sum(int x1,int y1,int x2,int y2){
	if(!x1&&!y1)return sum[x2][y2];//左上角为0，同定义
	if(!x1)return sum[x2][y2]-sum[x2][y1-1];//左上角的行为0，抽象为多行的一维前缀和
	if(!y1)return sum[x2][y2]-sum[x1-1][y2];//左上角的列为0，抽象为多列的一维前缀和
	return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}
int main（）{
	pre_sum();
	cout<<get_sum(1,1,2,2)<<" "<<get_sum(0,1,1,3);
	return 0;
}
//（1，1）到（2，2）的和 18
//（0，1）到（1，3）的和 35

arr

1	5	6	8
9	6	7	3
5	3	2	4

sum

1	6	12	20
10	21	34	45
15	29	44	59

二维差分

d[x1][y1]+=V,
d[x2+1][y1]-=V
d[x1][y2+1]-=V
d[x2+1][y2+1]+=V

arr

1	5	6	8
9	6	7	3
5	3	2	4

（0，0）到（2，1）+3
（1，1）到（2，2）-1操作

drr

3	0	-3	0	0
0	-1	0	1	0
0	0	0	0	0
-3	1	3	-1	0

sum前缀和

3	3	0	0	0
3	2	-1	0	0
3	2	-1	0	0
0	0	0	0	0

arr

4	8	6	8
12	8	6	3
8	5	1	4

#include<iostream>
using namespace std;
const int n=3，m=4;
int g[n][m]={{1,5,6,8},
			 {9,6,7,3},
			 {5,3,2,4} }
int sum[n][m];
int d[n+1][m+1];
void pre_sum(){
	sum[0][0]=g[0][0];//第一个
	for(int i=1;i<n;i++)sum[i][0]=sum[i-1][0]+d[i][0];//第一列
	for(int j=1;j<m;j++)sum[0][j]=sum[0][j-1]+d[0][j];//第一行
	for(int i=1;i<n;i++){
		for(int j=1;j<m;j++){
		sum[i][j]=d[i][j]+sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1];//g为右下角
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			g[i][j]+=sum[i][j];
		}
	}
	memsert(d,0,sizeof d);
	memsert(sum,0,sizeof sum);
}


void add(int x1,int y1,int x2,int y2,int v){//矩阵修改
	d[x1][y1]+=v;
	d[x2-1][y1]-=v;
	d[x1][y2+1]-=v;
	d[x2+1][y2+1]+=v;
}
void print(){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++)cout<<g[i][j]<<endl;
		cout<<endl;
	}
}
void printD(){
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)cout<<d[i][j]<<endl;
		cout<<endl;
	}
} 

}
int main（）{
	add(0,0,2,1,3);
	add(1,1,2,2,-1);
	pre_sum();
	print();
	return 0;
}//O(1)的操作
//O（n*n）的查询