二维差分模板题
https://www.acwing.com/problem/content/800/
同一维差分一样的思想,重要的也是时刻保证a[i]=b[0]+b[1]+...+b[i]
在二维则是:a[i][j]=b[0][0]+b[0][1]+...b[0][n]+b[1][0]+b[1][2]+..+b[i][j],也就是b的一个小矩阵之和是a[i][j]
要使得一个矩阵内的元素都加上C,二维的差分可以将O(N^2)->O(1)
因为要时刻确保a矩阵是b矩阵的前缀和,所以我们更改b矩阵,就会导致a矩阵的值发生变化(a数组也是b数组所构成的)
因此如果我们在b[x1][y1]上加上c,由于a是由b组成的,那么a[x1][y1]~a[n][n]这个范围的矩阵都会加上c
只要在b[x1[y2+1]上减去c,b[x2+1][y1]上减去c,b[x2+1][y2+1]上加上c,就可以使得a[x2+1][y2+1]~a[n][n]的值不变,这样就满足了题意
关键操作:
还有一点关键的是,如何构造差分矩阵b(满足a是b的前缀和)
由于a是b的前缀和,我们认为a,b初始没有值,那么对b赋与适当的值就能构造出原来的a(只要满足a是前缀和即可)
那么实际上,我们只需要让b[i][j]在(i,j)~(i,j)这个范围上每次+=c(c传入的是a[i][j]),原来a是0,但是由于b[i][j]=c了,那么a[i][j]=0+0+...+c,也就是a[i][j]成为了原来的a[i][j]
但是要满足原来的前缀和性质,如果只是这样操作的话,a[i][j]后面的值都会加上一个c,因此我们需要减的操作
同样的将b[x1][y2+1]减去c,b[x2+1][y1]减去c,这样a[x2+1][y2+1]又多减去了一遍c(因为a[x2+1][y2+1]是由b[x1][y2+1],b[x2+1][y1]等构成的),因此再加上c
b这样操作4步之后,仅仅只有b[x1][y1]满足了前缀和以及恢复原来的a[x1][y1],因此我们需要对所有点这样操作一遍,恢复所有的a[i][j],满足所有的a是b的前缀和
对所有点这样操作4步,每个点都加上了a[i][j],但是周围都减去或加上了c,这样是使得b始终满足差分的性质
那么实际上,这样的操作就是我们的关键差分操作,也就是只对[x1][y1]~[x2][y2]产生影响,对其他范围无影响
这样,我们知道b何处减去c,何处加上c,可以满足a是b的前缀和,具有通用性,即i,j是何数都满足这样的操作
大佬的原话:我们可以先假想a数组为空，那么b数组一开始也为空，但是实际上a数组并不为空
因此我们每次让b数组以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 c=a[i][j]，等价于原数组a中(i,j) 到(i,j)范围内 加上了 a[i][j] ,因此执行n*m次插入操作，就成功构建了差分b数组.
#include<iostream>
using namespace std;
const int N = 1e3+10;
int num[N][N],b[N][N];
int n,m,q;
int x1,y1,x2,y2,c;
void insert(int x1,int y1,int x2,int y2,int c)
{
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
cin >> n >> m >> q;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin >> num[i][j];
insert(i,j,i,j,num[i][j]);//构建差分矩阵
}
while(q--)
{
cin >> x1 >> y1 >> x2 >> y2 >> c;
//差分原理
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
//构造前缀和,即构造加过c的矩阵a
b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
cout << b[i][j] << " ";
puts("");
}
return 0;
}标签：x1,int,矩阵,差分,798,x2,y1,y2 From： https://www.cnblogs.com/lxl-233/p/17153600.html