差分和前綴和其實是一對逆操作，這里將會對前綴和和差分是怎么實施的，如何理解，以及對應一維和二維陣列的情況，
前綴和：換言之，就是前n項和，也就是高中學習數列時的Sn；
Sn = a1+a2+……an；
Sn+1 = a1+a2+……an+an+1 = Sn+an+1；
應用：如果要求從l到r的數字之和，我們不需要遍歷求和了，只需要呼叫前綴和序列的Sr和Sl-1，ans = Sr - Sl-1;
求（x1，y2） 到 （x2，y2）這個子矩陣之和又怎么求呢？
二維陣列求前綴和：
首先，我們要明白前綴和陣列中的這個b[i][j]代表了什么 ；
因為求的是子矩陣之和，我們的b[i][j]表征的是從[1][1]到[i][j]的子矩陣之和；
那么（x1,y1） 到 （x2,y2）的子矩陣之和 ans = b[x2][y2] -b[x1-1][y2] -b[x2][y1-1] +b[x1-1][y1-1] ;
圖示：
亮橙色是最終需要的，我們剪掉兩個紅色部分后，還應加上被重復減去的藍色部分，
板子：
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int a[maxn][maxn],b[maxn][maxn];
int main()
{
int n,m,q;
cin >> n >> m >> q;
//進行資料的讀入
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d",&a[i][j]);
//進行資料的處理,求前綴和
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]+a[i][j];
}
}
//進行查詢
for(int i = 1; i <= q; i++){
int x1,x2,y1,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",b[x2][y2]-b[x2][y1-1]-b[x1-1][y2]+b[x1-1][y1-1]);
}
return 0;
}
差分：因為一維和二維不同，我們可以單純的將差分理解為前綴和的逆運算，
應用：可以多次維護一個區間內資料的修改，
一維的情況：b[i] = a[i] -a[i-1]; b[l]+=c; b[r+1]-=c;
二維的情況：對于（x1,y1）, (x2,y2) 子矩陣加c，因為這是差分矩陣，我們做如下操作；
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
圖示：
橙色部分是指+=c的操作對于求前綴和的時候會直接管到矩陣右下角，紅色部分是用于-=c抵消掉+=c的操作，而藍色部分是因為重復了一次-=c 的操作，需要單獨+=c一次用于抵消，
值得注意的是，我們為了得到差分矩陣，我們先令其中的值全部為0，然后再把插入原矩陣中的值，相當于給（i，j）到（i，j）進行加1操作.
所以我們可以單獨寫一個insert函式，
板子：
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int a[maxn][maxn],b[maxn][maxn],c[maxn][maxn];
void insert(int x1,int y1,int x2,int y2,int c){
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
int n,m,q;
cin >> n >> m >> q;
//進行資料的讀入
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
scanf("%d",&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]);
}
}
//進行改變值的操作
for(int i = 1; i <= q; i++){
int x1,x2,y1,y2,c;
scanf("%d %d %d %d %d",&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[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+b[i][j];
}
}
//輸出ans
for(int i = 1;i <= n; i++){
for (int j = 1; j <= m; j ++ ){
printf("%d ",c[i][j]);
}
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/424948.html
標籤：其他
下一篇：CSRF跨站請求偽造漏洞分析