题解 | 【模板】二维差分

我们需要处理一个矩阵的多次子矩阵加法操作。直接对每个子矩阵元素逐个加k的方法在q很大时会很慢（O(qnm)）。为了高效处理，可以使用二维差分数组的方法，将每次子矩阵加k的操作转换为对差分数组的四个角的操作（O(1)），最后通过计算差分数组的前缀和来得到最终矩阵（O(n*m)）。

#include <iostream>
using namespace std;

long long a[1002][1002];  // 原矩阵
long long d[1002][1002];  // 差分数组

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];
        }
    }
    
    // 处理每个操作
    while (q--) {
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        d[x1][y1] += k;
        d[x1][y2+1] -= k;
        d[x2+1][y1] -= k;
        d[x2+1][y2+1] += k;
    }
    
    // 计算前缀和得到最终矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1];
            a[i][j] += d[i][j];
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

#牛客春招刷题训练营# +https://www.nowcoder.com/discuss/726480854079250432