c++ 题解 | #【模板】二维差分#

二维差分
假设a是输入的原矩阵，目标是给定矩形范围，在O(1)时间内将给定矩形范围子矩阵所有值都加上c。可以利用差分的方式。假设b是a的二维差分矩阵，那重点是：a是b的前缀和矩阵。即a[i][j]是b矩阵左上角(1,1)到右下角(i,j)的子矩阵和。 那类似于一维差分，当在差分矩阵b上进行加c，对应的其前缀和矩阵a（原始矩阵）就会影响到了起始点之后的空间的值（它们是包含加c了的矩阵b的前缀和矩阵a中部分）

1. 那在b上某个矩形上加了c，是如何影响其前缀和矩阵a的呢：
   假设矩形左上角是(x1,y1)，矩形右下角是(x2,y2)，在输入的矩阵a中红色区域的值都加上c。则有：
   当 b[x1][y1] += c ： 如图，让图1中所示的矩阵a中蓝色区域的值都加上了c。
   当 b[x1][y2+1] -=c ，则让a中绿色区域的值都减去了c
   当 b[x2+1][y1] -= c，则让a中黄色区域的值都减去了c
   当 b[x2+1][y2+1] += c， 则让a中紫色区域都加上了c
   目标是从蓝色框减去绿色和黄色，但多减了一个紫色区域，所以最后再加上一个紫色区域。
   

2. 如何构造差分矩阵b呢
   将上面四个操作封装成一个insert函数，不断调用insert函数，传入的c是a[i][j]

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1010;
typedef long long LL;
LL a[N][N], b[N][N];
void insert( int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2 + 1][y1] -= c;
    b[x1][y2 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

int main() {
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            scanf("%lld", &a[i][j]);
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            insert(i, j, i, j, a[i][j]);
        }
    int x1, y1, x2, y2, c;

    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);

    }
    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] - b[i - 1][j - 1];
        }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++) {
            printf("%lld ", b[i][j]);
        }
        printf("\n");
    }
        
    return 0;
}
// 64 位输出请用 printf("%lld")