一维前缀和、二维前缀和与一维差分、二维差分

前缀和

1.一维前缀和

引入：有一串长度为n的数列a1,a2,a3......an,再给出m个询问，每次询问给出L，R两个数，要求给出区间[L,R]里的数的和

朴素方法：对于m次询问，每次都遍历一遍所给的区间，计算出答案，时间复杂度O(n*m)；

利用前缀和：我们定义前缀和sum[i]表示a1+a2+...+ai；区间[L,R]里的数的和即为sum[R]-sum[L-1]，时间复杂度降到O(n+m);

void init()
{
sum[0]=0;
for(int i=1;i<=n;i++)
	sum[i]=sum[i-1]+a[i];
}
void query(int l,int r)
{
	return sum[r]-sum[l-1];
}

2.二维前缀和

 

引入：如图所示，有一个n*m的数字矩阵，给出q个询问，每次询问给出x1,x2,y1,y2四个数，要求给出区间[x1,y1][x2,y2]里的数的和

朴素方法：对于q次询问，每次都遍历一遍所给的区间，计算出答案，时间复杂度O(n*m*q)；

利用前缀和：我们定义前缀和sum[i][j]表示a11+a12+...+aij的和，例如，我们求④这个区域数值的和，我们由前缀和的定义可以知道：sum[x2][y2]=①+②+③+④，sum[x2][y1-1]=①+②，sum[x1-1][y2]=①+③，sum[x1-1][y1-1]=①，那么我们就能知道区间[x1,y1][x2,y2]里的数的和=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]；时间复杂度为O(n*m+q)；

int init()
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++) 
		sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];

}
int query(int x1,int y1,int x2,int y2)
{
	return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
}

差分

1.一维差分

引入：有一串长度为n的序列a1,a2,a3......an，有两种修改操作：①：将a[L]~a[R]内的元素都加上p；②：将a[L]~a[R]内的元素都减去p。进行m次修改操作之后有q个查询：询问求a[L]-a[R]内的元素之和。

朴素方法：对于m次操作，每次将区间a[L]~a[R]里的数都加p或减去p，最后求一次前缀和。时间复杂度O(M*n+q)；

利用差分：cha[]存的就是差分

void init(int l,int r,int p)//在区间[l,r]中每个数加p 
{
    cha[l]+=p;
	cha[r+1]-=p;
}
void update() 
{
    for(int i=1;i<=n;i++)
    {
    	a[i]=a[i-1]+cha[i];
    	sum[i]=sum[i-1]+a[i];
    }
}

时间复杂度可以到O(1)处理，O(n)求和;

为什么这么些呢？我们假设原序列a[1]=0，a[2]=0，a[3]=0，a[4]=0，a[5]=0;

我们给出操作:区间[1,4]加3，区间[2,3]加2，区间[2,4]减1；

2.二维差分

引入：有一串序列a11,a12,a13......ann，有两种修改操作：①：将a[x1][y1]~a[x2][y2]内的元素都加上p；②：将a[x1][y1]~a[x2][y2]内的元素都减去p。进行m次修改操作之后有q个查询：询问求a[x1][y1]~a[x2][y2]内的元素之和。

与一维差分类似

void init(int x1,int y1,int x2,int y2,int p)
{
    a[x1][y1]+=p;
    a[x1][y2+1]-=p;
    a[x2+1][y1]-=p;
    a[x2+1][y2+1]+=p;
}
void update()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
        	a[i][j]+=a[i][j-1]+a[i-1][j]-a[i-1][j-1];
        	sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
		}
}