懒得画图所以没有图。。
对于二维差分的定义，百度百科是这么说的

顾名思义，就是在矩阵中，一行（一列）的元素与上一行（上一列）对应元素的差值，依次排列在上一行（上一列）元素对应所在位置。

（好像说的是矩阵差分，但是问题不大）

但是只要你用模板代码打出一个差分数组就会发现这个数组的排列并不规律，换句话说我并没有看懂这个。。

因此我们完全可以忽略差分数组一个点的意义

只需要抓住其前缀和是原来数值的特点进行修改即可

而每次更新时都可以将其拆解为两个一维的数组去处理

#include<bits/stdc++.h> #define R register int using namespace std; const int maxn=1002; int m,n,q; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘) if(ch==‘-‘) f=-1,ch=getchar(); while(ch>=‘0‘&&ch<=‘9‘) x=(x<<3)+(x<<1)+ch-‘0‘,ch=getchar(); return x*f; }int a[maxn][maxn]; inline void insert(int x1,int y1,int x2,int y2,int v) { a[x1][y1]+=v; a[x2+1][y1]-=v; a[x1][y2+1]-=v; a[x2+1][y2+1]+=v; } int main() { int i,j; n=read();m=read();q=read(); for( i=1;i<=n;i++) for( j=1;j<=m;j++) { int x=read(); insert(i,j,i,j,x); } for( i=1;i<=q;i++) { int x1=read(),y1=read(),x2=read(),y2=read(),c=read(); insert(x1,y1,x2,y2,c); } for(i=1;i<=n;i++) for( j=1;j<=m;j++) a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1]; for( i=1;i<=n;i++) { for( j=1;j<=m;j++) printf("%d ",a[i][j]); puts(""); } return 0; }

ACwing ： 798. 差分矩阵

标签：

原文地址：https://www.cnblogs.com/smartljy/p/11777466.html