【模板】二维差分

难度：3星

类似二维前缀和的套路，开一个差分数组 $sumsum$，对于左上角 $(x_1,y_1)(x\_1,y\_1)$ 、右下角 $(x_2,y_2)(x\_2,y\_2)$ 的矩形所有数加上 $kk$ ，我们只需要把 $sum[x_1][y_1]sum[x\_1][y\_1]$ 加上 $kk$ ， $sum[x_2+1][y_1]sum[x\_2+1][y\_1]$ 减去 $kk$， $sum[x_1][y_2+1]sum[x\_1][y\_2+1]$ 减去 $kk$，$sum[x_2+1][y_2+1]sum[x\_2+1][y\_2+1]$ 加上 $kk$ 。在所有操作结束以后统一做二维前缀和就可以了。

#include<bits/stdc++.h>
using namespace std;
long long a[1010][1010],sum[1010][1010];
int main(){
    int n,m,q,i,j;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    while(q--){
        int x1,y1,x2,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        sum[x2+1][y2+1]+=k;
        sum[x1][y2+1]-=k;
        sum[x2+1][y1]-=k;
        sum[x1][y1]+=k;
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            sum[i][j]+=sum[i-1][j];
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            sum[i][j]+=sum[i][j-1];
            cout<<sum[i][j]+a[i][j]<<" ";
        }
        cout<<"\n";
    }
    
    
}