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

和#【模板】差分#的思路完全一致。
使用一个二位数组sum来记录每一位改变的信息，然后通过求前缀和的形式求出每一位一一对应的改变值。最后将sum中的每一个元素与原始数组arr中对应的元素加起来即可得到结果数组。
唯一有区别的地方在记录改变信息以及求前缀和上的操作略微复杂化。这里记录的方式与求前缀和的方式是一一对应的。若记录时以列为起点，则求前缀和时也要以上一列作为迭代对象；若记录时以行为起点，则求前缀和时也要以上一行为迭代对象。
这里采用以列为起点的方式，即处理输入的(x1,y1), (x2,y2), k时，将(x1, y1), (x1+1,y1), ..., (x2,y1)，即待改变矩阵的第一列，全部加上k。将(x1, y2+1), (x1+1,y2+1), ..., (x2,y2+1)，即带改变矩阵的右侧边界，全部减去k。在求前缀和时，则以同一行前一列作为迭代对象，即sum.at(i).at(j)+=sum.at(i).at(j-1)。得到前缀和数组sum后，直接将其中元素与arr中对应项相加即可得到结果数组。

这种做法时间复杂度为O(nm)，体现在二维数组的遍历上。空间复杂度为O(nm)，体现在sum，与二维数组相同大小的前缀和数组上。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m, q;
    cin >> n >> m >> q;
    vector<int> tempi(m, 0);
    vector<vector<int>> arr(n, tempi);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> arr.at(i).at(j);
        }
    }
    vector<long long> templ(m, 0);
    vector<vector<long long>> sum(n, templ);
    for(int i = 0;i < q;i++){
        int x1, y1, x2, y2, k;
        cin >> x1 >> y1 >> x2 >> y2 >> k;
        for(int j = x1 - 1;j < x2;j++){
            sum.at(j).at(y1 - 1) += k;
        }
        for(int j = x1 - 1;y2 < m && j < x2;j++){
            sum.at(j).at(y2) -= k;
        }
    }
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if (j != 0){
                sum.at(i).at(j) += sum.at(i).at(j - 1);
            }
            cout << arr.at(i).at(j) + sum.at(i).at(j) << " ";
        }
        cout << endl;
    }
    return 0;
}