AcWing 798 差分矩阵(二维差分)_二维差分公式

题目链接 ： 点击查看

题目描述 ：

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1, y1, x2, y2, c, 其中 (x1, y1) 和 (x2, y2) 表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。请你将进行完所有操作后的矩阵输出。

输入输出 ：

输入

3  4  3
1  2  2  1
3  2  2  1
1  1  1  1
1  1  2  2  1
1  3  2  3  2
3  1  3  4  1

输出

2  3  4  1
4  3  4  1
2  2  2  2

题目分析：

本题的难点在于如何构建二维差分数组和如何通过操作差分数组来使得区域上的数全部加c。关于如何构建二维差分数组，可以参考二维前缀和及一维差分的数组构建方式，二维前缀和构建公式为s[ i ][ j ] = a[ i  - 1 ] [ j ] + a[ i ] [ j - 1 ]  - a[ i - 1 ] [ j - 1], 一维差分构建公式为 b [ i ] = a[ i ] - a [ i - 1 ]，且前缀和与差分互为逆运算，因此通过简单类比可以得到  b[ i ] [ j ] = a [ i ] [ j ] - a [ i - 1 ] [ j ] - a [ i ] [ j - 1 ] + a [ i  - 1 ] [ j  - 1 ], 这个即为二维差分数组的构建公式。同样类比于一维差分更新原数组方式, 二维差分如若更新原数组的值，需要以下4个公式 1 . b[ x1 ] [ y1 ] += c ; 即(x1, y1) 右下方的矩形中的数全部加上c。2 . b [ x1 ] [ y2 + 1 ] -= c 这里由于边界问题 因此要y2 + 1防止选中y2边界上的点，其他同 1，只不过为减去c 。3 .b[ x2 + 1] [ y1 ] -= c 同样要考虑边界问题，其他同 2 。 4 . b [ x2 + 1 ] [ y2 + 1] +=c 防止重复减的发生。最后，要更新原数组则变换二维差分公式为 a[ i ] [ j ] = a [ i - 1] [ j ] + a [ i ] [ j - 1] - a[ i - 1 ] [ j - 1 ]。

代码 ：

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e3 + 7;
int a[N][N], b[N][N];
int n, m, q;
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i ++ ) {
		for (int j = 1; j <= m; j ++ ) {
			cin >> a[i][j];//初始化原矩阵 
		}
	}
	for (int i = 1; i <= n; i ++ ) 
	    for (int j = 1; j <= m; j ++ ) {
	    	b[i][j] = a[i][j] - a[i][j - 1] - a[i - 1][j] + a[i - 1][j - 1]; //构建差分矩阵 
		}
	while (q -- ) {
		int x1, x2, y1, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		b[x1][y1] += c;
		b[x2 + 1][y1] -= c;
		b[x1][y2 + 1] -= c;
		b[x2 + 1][y2 + 1] += c;  
	} 
	for (int i = 1; i <= n; i ++ ) {
	    for (int j = 1; j <= m; j ++ ) {
	    	a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]; //更新原矩阵 
		}
    }
    for (int i = 1; i <= n; i ++ ) {
	    for (int j = 1; j <= m; j ++ ) {
	    	cout << a[i][j] << " "; 
		} 
	    cout << endl;
	} 
	return 0;
}

--------------------------------------------------------------------------------------

在此我们给出本题核心公式 

给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c