题解 | 【模板】二维差分

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m, q;
    while (cin >> n >> m >> q) {
        vector<vector<long long>> vec(n + 1, vector<long long>(m + 1, 0));
        vector<vector<long long>> diff(n + 2, vector<long long>(m + 2, 0));

        // 读取初始数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> vec[i][j];
            }
        }
        //以下为二维差分数组做法：
        for (int i = 0; i < q; i++) {
            int x1, y1, x2, y2, k;
            cin >> x1 >> y1 >> x2 >> y2 >> k;

            diff[x1][y1] += k;
            diff[x1][y2 + 1] -= k;
            diff[x2 + 1][y1] -= k;
            diff[x2 + 1][y2 + 1] += k;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 计算前缀和
                diff[i][j]+= diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
                //这个公式怎么来的最开始没看懂，具体看https://blog.csdn.net/melonyzzZ/article/details/128448400，实际上就是求按四角调整完的diff矩阵的前缀和矩阵，一模一样
                // 更新原数组
                vec[i][j] += diff[i][j];
                cout << vec[i][j] << ' ';
            }
            cout << endl;
        }
        //以下为简单当成m列一维差分数组进行处理，本题可通过不超时
        // // 处理区间更新
        // for (int i = 0; i < q; i++) {
        //     int x1, y1, x2, y2, k;
        //     cin >> x1 >> y1 >> x2 >> y2 >> k;

        //     // 对每一列进行更新
        //     for (int j = y1; j <= y2; j++) {
        //         diff[x1][j] += k;
        //         if (x2 + 1 <= n ) {
        //             diff[x2 + 1][j] -= k;
        //         }
        //     }
        // }

        // // 计算最终结果
        // for (int i = 1; i <= n; i++) {
        //     for (int j = 1; j <= m; j++) {
        //         // 计算前缀和
        //         diff[i][j] += diff[i - 1][j];
        //         // 更新原数组
        //         vec[i][j] += diff[i][j];
        //         cout << vec[i][j] << ' ';
        //     }
        //     cout << endl;
        // }
    }
    return 0;
}