noip数据结构与算法 之 基础小算法 4 二维差值维护

二维差值维护问题实际上是对一维差值维护问题的扩展，相信来看二维差值维护的各位都已经对一维差值维护问题有足够的认识了。下面先看一下二维差值维护的问题。 

问题描述：

已知一个n*n的矩阵a，有m次操作，每次操作给定,,,,k五个数，使得以(,)为左上角以(,)为右下角的子矩阵内所有数加上k。注意这个子矩阵包含(,)和(,)两个元素。

输入数据：

第一行n和m，接下来有n行，每行有n个数，表示矩阵a，接下来有m行，每行有五个数,,,,k，详细解释参考问题描述。

输出数据：

共n行，每行n个数，表示经过m次操作之后的矩阵a。

输入样例：

5 2

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

21 22 23 24 25

2 2 4 4 3

3 3 5 5 2

输出样例：

1 2 3 4 5

6 10 11 12 10

11 15 18 19 17

16 20 23 24 22

21 25 28 29 27

数据范围：

是int范围内的任意整数，输入数据保证+k在int的范围内

对于这个问题，我们同样是要寻找一种方式使我们在常数级的时间复杂度内做出对某一区间的矩阵进行加k的操作。相比于一维的差值维护不同的是，这里我们维护的是一个矩阵。

这里问题就来了，在一维的差值维护里面，我们可以轻易求得一个数与其前一个数的差值。但是在矩阵里，这个差值如何计算呢？

让我们从差值的目的进行分析，我们求得一个数和它前一个数的差值，是为了用前一个数经过某个变换能够得到这个数，而且这个变换不会因为我们的操作而发生意外的改变。所以我们找到了一维的数列里面最简单的si-si-1的操作。

对于一个矩阵而言呢？我们可以用矩阵中任意2*2子矩阵来推得这个2*2子矩阵右下位置的数在矩阵中的差值。

                                                                                    

对于上图2*2的子矩阵，我们可以求得d处的差值，这个公式就是a+d-b-c，简单来说就是主对角线的和减去副对角线的和。

重新思考一下这个过程，假设有一个原矩阵a，我需要一个算法s=f(a)表示把a矩阵转换成一个差值矩阵s。这个差值的算法f(a)就是，形象的去看这个公式就是上面图里的那个，我取矩阵a中任意2*2的子矩阵，右下角元素的差值就是这个2*2子矩阵主对角线和(对应)减去副对角线的和（对应）。而对于最顶的一行和最左的一列，我们按照一维差值维护的方式维护即可。这样我们可以保证，我们每一个数的差值计算只需要依赖它左侧，上侧和左上侧3个数，而逆推的过程，我们也只需要知道差值和之前这三个数的值即可。我们可以直接算出差值数组，也可以自上而下，自左而右的算出原数组。

下面我举一个简单的例子：

求矩阵任意一个元素的差值，这里以(2,2)为例，这个过程如下图所示：

我们可以直观的看到差值数组的求法，利用这样的过程，就可以求出差值数组s,这个过程是O()的。现在考虑逆推的过程，对于差值数组的原数，我们需要拿这个数字左侧，左上侧和上侧数字的原数和这个数字的差值求得，简单来说就是，而一开始的就等于，所以我们自上而下，自左而右的递推就可以实现原数组的求解。简单来说如下：

首先单独看第一行和第一列，第一行差值数组全为1，我们按照一维差值维护的方式处理，即第一行每一个与前一个的差值是1，恢复过来就是1,2,3,4,5。第一列类似，只不过差值是5，那么第一列恢复过来就是1,6,11,16,21。

那么现在的情况就是，我知道(1,1)是1，(1,2)是2，(2,1)是6，(2,2)的差值是0，我应该怎么求(2,2)处的值呢？

通过刚刚求出的等式可知，所以，?=0+2+6-1=7，问题解决！

实现了由原数组到差值数组的计算以及差值数组逆推原数组的计算，现在我们应该考虑，如何更改差值数字中的值才能达到对原数组某个子矩阵里的所有数同时增加一个k值的目的呢？

下面我们考虑修改差值数组里某个数的情况，还是拿上面的例子为例。现在我把差值数组里(2,2)的那个数0加上一个2，它变成了2。那么这个加2之后对我们的原数组发生了什么变化呢？我们来把新的这个差值数组逆推一下得到原数组：

你可以很明显的看到，以(2,2)为左上以(5,5)为右下的子矩阵里的所有数字都增加了2，这似乎满足了我们的要求。但是不完全满足，我们只是获得了一个操作方式，这个操作是改变差值数组中(x,y)的那个数值，并且改变的结果是让以(x,y)为左上以(5,5)为右下的整个子矩阵在原数组里改变那个数值。

接下来我们继续操作，以实现把以(2,2)为左上(4,4)为右下的子矩阵（现在我们把它记作(2,2)->(4,4)，下同）里的所有数加2。很庆幸的，在第一步操作中，我们已经把(2,2)->(5,5)的整个子矩阵中的数值都加了2，现在我发现(2,5)->(5,5)的矩阵。以及(5,2)->(5,5)的矩阵都多加了一个2，因此我们把它减回来，具体操作就是，把差值数组里(2,5)和(5,2)的位置都-2。这样我们推出来的结果就很像我们想要的结果了。

等等！貌似还有不对的地方。按照我们的计算方式(5,5)->(5,5)这个矩阵被加了一次2减了两次2。所以我们最后还要把(5,5)->(5,5)这个矩阵加2。

因此我们把(2,2)->(4,4)的矩阵的所有数字加2时要做四个操作。改变差值数组(2,2)处的值，使其加2；改变差值数组(2,5)和(5,2)处的值，使其减2；改变(5,5)处的值，使其加2。

最后总结一下我们得到的结果，首先，改变差值数组里第(x,y)的数意味着把原数组(x,y)->(,)的所有数都改变了这个数。因此我们想要让(,)->(,)的子矩阵里所有数都加上k，我们只需要对差值数组里(,)+k，(,+1)-k，(+1,)-k，(+1,+1)+k即可。

最后分析一下复杂度，我们不难看出，计算差值数组是O()；每一次操作是O(4)，一共是m次操作，因此所有操作就是O(m)；由差值数组计算原数组也是O()；总计是O(​​​​​​​+m)的时间复杂度。

以上就是对二维差值维护问题的介绍。

我的代码如下：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <algorithm> 
using namespace std;

const int MAXN=1010;

int n,m,a[MAXN][MAXN],s[MAXN][MAXN];

//读入优化 
int read(){
	char ch=getchar();
	bool fl=0;
	int r=0;
	if(ch=='-'){
		fl=1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9'){
		r*=10;
		r+=ch-'0';
		ch=getchar();
	}
	return fl?-r:r; 
}

//输出优化 
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9){
		write(x/10);
	}
	putchar(x%10+'0');
}

int main(){
	freopen("in.txt","r",stdin);
	freopen("std.txt","w",stdout);
	n=read();
	m=read();
	a[0][0]=read();
	s[0][0]=a[0][0];
	for(int i=1;i<n;++i){
		a[0][i]=read();
		s[0][i]=a[0][i]-a[0][i-1];
	}
	for(int i=1;i<n;++i){
		a[i][0]=read();
		s[i][0]=a[i][0]-a[i-1][0];
		for(int j=1;j<n;++j){
			a[i][j]=read();
			s[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1];//O(n^2)的生成差值数组 
		}
	}
	for(int i=0;i<m;++i){
		int x1,y1,x2,y2,k;
		x1=read();
		y1=read();
		x2=read();
		y2=read();
		k=read();
		--x1,--y1,--x2,--y2;
		s[x1][y1]+=k;
		if(y2+1<n)s[x1][y2+1]-=k;
		if(x2+1<n)s[x2+1][y2]-=k;
		if(y2+1<n && x2+1<n)s[x2+1][y2+1]+=k;//O(4)的操作，所有操作一共O(m) 
	} 
	write(s[0][0]);
	putchar(' ');
	for(int i=1;i<n;++i){
		s[0][i]+=s[0][i-1];
		write(s[0][i]);
		putchar(' ');
	}
	putchar('\n'); 
	for(int i=1;i<n;++i){
		s[i][0]+=s[i-1][0];
		write(s[i][0]);
		putchar(' ');
		for(int j=1;j<n;++j){
			s[i][j]=s[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
			write(s[i][j]);
			if(j!=n-1)putchar(' ');//输出接着O(n^2)
			else putchar('\n');
		}
	}
	//总复杂度O(m+n^2) 
	return 0;
}