前缀和、差分

一、前缀和

1、一维前缀和

思路：

求前n个数的和，可以使求[l,r]的和从复杂度O(n)变为复杂度为O(1)的

代码模板：

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int  a[N],s[N];
int main()
{
	scanf("%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+a[i];
	while(m--)
	{
		int l,r;
		scanf("%d %d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);
	}
	return 0;
}

2、二维前缀和

思路：

二维前缀和的每一个点，代表这一点左上矩形所有元素的和。

想算一个矩形的和，给定如图两个点的坐标分别为（x1,y1）,（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=10010;
int a[N][N],s[N][N];
int n,m,q;//n是行数，m是列数,q是询问次数 
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);//将所有数字存在a矩阵中 
	}
	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];//计算左上矩阵的和放到这一点的s矩阵中 
	}
	while(q--)
	{
		int x1,x2,y1,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;
}

3、一维差分

思路：

差分记录的是两个相邻数的差，与前缀和是逆运算。对于差分不需要考虑构造，因为刚开始可以默认a数组（即原数组）均为0，然后通过将原数组每个数分别插入来构造差分数组。先明白a数组是b数组的前缀和，用前缀和反过来求差分

一般用到差分都是将某一段的数都+-一个数字，用差分可以把时间复杂度从O(n)降到O(1)

代码模板:

#include<iostream>
using namespace std;
const int N=10010;
int n,m;
int a[N],b[N];//a是原数，b是差分 
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);
	}
	for(int i=1;i<=n;i++)
		b[i]+=b[i-1];		//将差分数组进行前缀和，得到的就是原数 
	for(int i=1;i<=n;i++)
		printf("%d ",b[i]);
	return 0;
}

4、二维差分

思路：

代码模板：

#include<iostream>
using namespace std;
const int N=1010;
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[x2+1][y1]-=c;
	b[x1][y2+1]-=c;
	b[x2+1][y2+1]+=c;

}
int main()
{
	scanf("%d %d %d",&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++)
			insert(i,j,i,j,a[i][j]);//将原数组的数依次插入，同时求出差分数组 
	while(q--)
	{
		int x1,y1,x2,y2,c;
		scanf("%d %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++)
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];//将差分矩阵求前缀和得到原数 
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			printf("%d",b[i][j]);
		puts("");
	}
	return 0;
}