【Acwing】差分矩阵

 

 图1：a和b数组映射表

由于a是b的前缀和数组，因此改变b[ x1][ y1]之后，受到影响的a中元素如右半图所示

   图2：求b数组的前缀和 

#include<bits/stdc++.h>
using namespace std;int n,m,q;
int a[1010][1010];
int b[1010][1010];int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>q;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){cin>>a[i][j];// 关于为什么要这么做，请看图1b[i][j] += a[i][j];b[i+1][j+1] += a[i][j];b[i][j+1] -= a[i][j];b[i+1][j] -= a[i][j];}int x1,y1,x2,y2,c;for(int i=1;i<=q;++i){cin>>x1>>y1>>x2>>y2>>c;b[x1][y1] += c;b[x2+1][y2+1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;}// 求前缀和，也就是由b数组得到变化后的a数组// 详见图2for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){b[i][j] -= b[i-1][j-1];b[i][j] += b[i][j-1];b[i][j] += b[i-1][j];cout<<b[i][j]<<' ';}cout<<'\n';}return 0;
}