题目描述

输入一个 n行 m列的整数矩阵，再输入 q个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)和 (x2,y2)
表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

这题最困扰我的地方有两点，第一点是为什么insert函数可以直接构建差分矩阵b，第二点是最后求前缀和的公式不太理解。
先给出最好理解的写法。

写法1，最简单直接

#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int 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;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j],
            b[i][j] = a[i][j] - a[i][j-1] - a[i-1][j] + a[i-1][j-1];//构建二维差分数组,直接定义法，不用insert函数
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> 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++)
        {
            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++)
        {
            printf("%d ", a[i][j]);//输出操作完所有步骤后的a[][]
        }
        printf("\n");
    }
    return 0;
}

写法2，技巧性强

#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int 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;
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
            insert(i,j,i,j,a[i][j]); //改动1
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> 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];  //改动2
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            printf("%d ", b[i][j]);//输出操作完所有步骤后的a[][]
        }
        printf("\n");
    }
    return 0;
}

共两点改动

改动1

第一点是通过insert函数直接求差分数组b，这样就不用用二维的差分公式了
原因是因为我们每次让b数组以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了a[i][j]，不断通过修改b，使得b满足是a的差分数组这个性质不变。

改动2

第二点是一个求二维前缀和的简化写法，但是我感觉不如不简化好理解。
原来的写法：a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j]; 这是直接用二维差分公式，
也可以直接在差分数组b上操作：b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1[j - 1] + b[i][j];
如何理解？此处右边旧的b[i][j]为差分数组的值，左边新的b[i][j]的含义已经可以理解为前缀和了，因此直接用新的b[i][j]替换掉旧的b[i][j]，所以循环结束后，b数组就成了前缀和数组（比较绕…
用+=化简后得到：b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1[j - 1] ;
好处应该是可以用一个数组就可以完成