牛客网【模板】二维差分（详解）c++

题目链接：【模板】二维差分

1.题目分析

类比一下，因为差分因为差分是在数组里的某一段同时加上一个K二维是在二维数组中选择一个词矩阵，让词矩阵中每一个元素都加上一个K 

2.算法原理

解法-:暴力解法 -> 模拟

你告诉我一个左上角和右下角，我直接来两层for循环把这个小矩阵遍历一遍，每次遍历的时候把每一个元素都加上一个K就可以了，针对每一次询问q，最差情况下会遍历整个数组一遍，所以关于模拟它的时间复杂度是O（q*n*m），1e5*1e3*1e3=1e11，肯定会超时的

解法二:利用差分矩阵解决问题

作用:快速处理“将二维数组中，某一个子矩阵统一加上或减去一个元素”的操作

在差分数组中，某一个格子执行 +k 操作，会影响以它为左上角，以[n,m]为右下角这样的一个矩阵中，所有的元素在求完前缀和之后，统一 +k

如果我在（x1，y1），（x2，y2）的位置写了一个+k，现在求差分矩阵求前缀合，求第一行的时候是不受影响的，但求到第二行（x1，y1）这个位置的时候，因为这个格子加上了个K，所以这个格子还原之后出来的值，也是加上一个K的，正好是对应a对应的格子，如果求的是左上角8个格子的前缀和，加完全部元素后会发现是在之前的基础上多加了一个K，就是在求三角形格子的前缀和时，求的是蓝色方块里面所有元素的和，因为（x1，y1）加了一个k，整体所有格子会在之前的基础上多加一个K，所以在（x1，y1）这里加上了一个K之后，以它为左上角对应的所有右下角的格子求前缀合的时候，求完之后都会在之前的基础上加一个K

此时（x1，y1）加完K后，再对差分数组求矩阵和，除了会加上蓝色的K还会加上红色的K，是要消除这个影响的，因为我们想达到的效果只是（x1，y1）到（x2，y2）的区间里面加K，解决这个问题只需要在（x2+1，y1）（x1，y2+1）位置上减去K就消除了影响，还有一个问题是在它们消除影响的区域有一块部分重合，也就是说这两个位置-K的时候，会让一个区域重复减了两次，此时我们在重合的地方写一个+K就可以了，整个操作只会影响红色的部分

此时性质就出来了，在（x1，y1），（x2，y2）这段区间统一加K的操作，在差分数组里面只需执行四个位置就可以了，f [ x1 ][ y1 ] += k；f [ x1 ][ y2+1 ] -= k；f [ x2+1 ][ y1 ] -= k；f [ x2+1 ][ y2+1 ] += k；

第一步：预处理差分数组
假设 a [ i ][ j ] = x，相当于以（i，j）为左上角，以（i，j）为右下角的子矩阵，加上一个x，直接带入差分性质就可以了

第二步：利用差分数组解决m次修改
每次修改告诉我左上角（x1，y1），右上角（x2，y2），在这个子矩阵里面统一加上一个k，代入到上面四个公式即可

第三步：如果还原出原始的矩阵
对差分数组来一次前缀和即可

代码：
 

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1010;
int n, m, q;
LL f[N][N]; // 差分矩阵

// 差分矩阵的性质
void insert(int x1, int y1, int x2, int y2, int k)
{
	f[x1][y1] += k, f[x1][y2 + 1] -= k, f[x2 + 1][y1] -= k, f[x2 + 1][y2 + 1] += k;
}
int main()
{
	cin >> n >> m >> q;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			int x;  cin >> x;
			insert(i, j, i, j, x);
		}
	}

	//处理q次修改操作
	while (q--)
	{
		int x1, x2, y1, y2, k;
		cin >> x1 >> y1 >> x2 >> y2 >> k;
		insert(x1, y1, x2, y2, k);
	}

	//利用前缀和还原出修改之后的数组
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
			cout << f[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}