[数据结构与算法]【无标题】

前缀和与差分

前缀和：表示一个数列的前n项和，理解为数组的话就是从下标为1到n（定义成数组时就从下标为1开始接收该序列）。

一维前缀和：

#include<iostream>
using namespace std;
int main()
{
	int i,a[5]={1,2,3,4,5},b[5]={0};
	for(i=0;i<=4;i++)
	{
		b[i]=b[i-1]+a[i];
		cout<<b[i]<<' ';
	}
	return 0;
} 

好处：用于求数组a某个区间（例如n1到n2）的和，利用前缀和数组b，直接相减（b[n2]-b[n1-1]）即可得到。

二维前缀和：

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]+a[i][j]+b[i-1][j-1];
  }
}

差分：是前缀和的逆运算，前缀和与差分数组是对应关系。例如数组a的前缀和为数组b，则b的差分数组为数组a。

差分数组：首先给定一个原数组a：a[1], a[2], a[3],,,,,, a[n]，然后我们构造一个数组b ： b[1] ,b[2] , b[3],,,,,, b[i]，使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]，也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。

一维差分:举一个例子数组a和数组b，数组b是a的前缀和数组，即有a[i]=b[i]-b[i-1]

二维差分：以（n1,m1）为左上角，(n2,m2)为右下角的矩阵都加上1，与一维差分类似。对差分数组(n1,m1)处加1，（n2+1,m1）处减1，（n1,m2+1）处减1，（n2+1,m2+1）处加1。