前缀和与差分：

前缀和：

• 一维：

#define N 10004
void _1(){
	int n, a[N], ans[N];
	scanf("%d",&n);
	for(int i = 1; i <= n; i++){scanf("%d",a+i);ans[i] += ans[i-1] + a[i] ;}
//	for(int i = 1; i <= n; i++)	cout<<ans[i]<<" ";cout<<endl;
	printf("%d",s[r] - s[l - 1]);
//求区间 [l,r] 区间和 即 a[l] + a[l+1] + ... + a[r] = S[r] - S[l - 1]
}

• 二维：

void _2(){
	cin>>n>>m>>q;
	for(int i = 1; i <= n; i++)
		for(int j =1; j <= m; j++)
			scanf("%d",&a[i][j]);
	//二维前缀和 
	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];
			
	while(q--){//询问次数 
		int x1,x2,y1,y2;//区间 [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]);
	}
} 

差分：

• 一维：

#include<bits/stdc++.h>
#define N 10005
using namespace std;
int n , m, a[N] ,b[N]; 
void insert(int l, int r, int c){
	b[l] += c;
	b[r + 1] -= c; 
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n; i++) scanf("%d",a+i);
	for(int i = 1; i <= n; i++)	insert(i, i, a[i]); //构造差分 
	while(m--){ int l,r,c;   scanf("%d%d%d",&l,&r,&c);   insert(l, r, c); }//m 次操作
	for(int i = 1; i <= n; i++) {
	   b[i] += b[i-1];//将差分数组前缀和回去	
	printf("%d ",b[i]);//原数组 a 加上 c 的数组 
	}
	return 0;
}

• 二维：

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

前缀和与差分：

原文：https://www.cnblogs.com/xswlQAQ/p/14427711.html