题解 | 【模板】二维差分

#include <iostream>
using namespace std;
#include<vector>
#define N 1e3
#define int long long 
signed main() {
   int n,m,q;
   cin>>n>>m>>q;
   vector<vector<int>>a(N,vector<int>(N));
   vector<vector<int>>diff(N,vector<int>(N));
   for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
           cin>>a[i][j];
    }
  }
  //构造差分数组 
  // 一维差分数组代表着增量  二维也是如此
  // 二维差分数组的 diff[i][j] 本质也是「增量」，是 a[i][j] 相对于 “上、左、左上” 的净增量；
  //   核心矛盾：“上” 和 “左” 都包含了 “左上”，导致直接减会重复，必须补回来。
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
         diff[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];  
    }
  }   //差分进行加减 代表对右下角所有都加减  依旧结合图形理解
   while(q--){
      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++){
         a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+diff[i][j];
    }
  }
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cout<<a[i][j]<<" ";
    }
    cout<<endl;
  }

}
// 64 位输出请用 printf("%lld")