前缀和以及二维前缀和在这里就不写了.
差分: 是前缀和的逆运算
ACWING https://www.acwing.com/problem/content/800/ 二维差分矩阵
每一个二维数组上的元素都可以用 (x,y) 表示, 对于某一元素 (x0,y0), 其前缀和就是以该点作为右下角以整个数组的起始点作为左上角的矩形区域内所有元素的和.[如下图的红色区域, 其中六个元素的和就是(x0,y0) 的前缀和]
- #include<cstring>
- #include<iostream>
- using namespace std;
- const int maxn=1010;
- int n,m,q;
- int a[maxn][maxn],b[maxn][maxn];
- 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>>a[i][j];
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- insert(i,j,i,j,a[i][j]);
- while(q--)
- {
- int x1,y1,x2,y2,c;
- 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++)
- 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]<<" ";
- cout<<endl;
- }
- }
参考博客:
ACwing 算法基础课听课笔记(第一章, 基础算法二)(差分)
来源: http://www.bubuko.com/infodetail-3304112.html