1、什麼是一維差分？
一維差分是一維字首和的逆運算,舉個栗子：
原數組與差分數組的關系：原數組前後兩項的差就是差分數組的值：\(b[i]=a[i]-a[i-1]\)
對于第1個差分數組的值，\(b[1]=a[1]-a[0]\),因為\(a[0]\)初始化為\(0\),是以\(b[1]=a[1]\),但也不妨礙我們按通用的方式進行了解。
差分數組與原數組的關系:差分數組的字首和是原數組:\(a[i]=b[1]+b[2]+b[3]+...+b[i]\)
2、一維差分的建構
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
上面就是建構的方法，我們來了解一下：
以\(a_1=9,a_2=3,a_3=5,a_4=4,a_5=2\)這個原始數組為例，根據上面的計算辦法建構差分數組：
第一步：
insert(1,1,9)
,就是
l=1
,
r=1
c=9
,那麼
b[1]=9
b[2]=-9
。
第二步：
insert(2,2,3)
l=2
r=2
c=3
b[2]=-9+3=-6
b[3]=0-3=-3
第三步：
insert(3,3,5)
l=3
r=3
c=5
b[3]=-3+5=2
b[4]=0-5=-5
第四步：
insert(4,4,4)
l=4
r=4
c=4
b[4]=-5+4=-1
b[2]=0-4=-4
第五步：
insert(5,5,2)
l=5
r=5
c=2
b[5]=-4+2=-2
b[2]=0-2=-2
3、一維差分用途
當我們要在某個區間\([l,r]\)的所有值都加上一個數\(x\)時：我們隻需要在差分數組中進行一加一減即可：\(b[l]+c，b[r+1]−c\)
為什麼呢？
以\(a[1]=9,a[2]=3,a[3]=5,a[4]=4,a[5]=2\)這個原始數組為例,現在要地\(a_2至a_4\)這個範圍内增加\(2\):
\(a[1]=b[1]\)
\(a[2]=b[1]+b[2]\)
\(a[3]=b[1]+b[2]+b[3]\)
\(a[4]=b[1]+b[2]+b[3]+b[4]\)
\(a[5]=b[1]+b[2]+b[3]+b[4]+b[5]\)
\(a[6]=b[1]+b[2]+b[3]+b[4]+b[5]+b[6]\)
現在要在\(a_2至a_4\)增加數字2，我們看看能不能通過增大\(b\)數組某兩個值的方法對它們進行維護。
比如\(b[2]+=2\),那麼受影響的是\(a[2]\)及後面所有的\(a\)數組元素，包括\(a[5],a[6]\),這樣還不行，因為我們隻要求變化到\(a[4]\),看來還需要再做點什麼，比如從\(b[5]\)中再減去數字2，這時我們驚喜的發現，從 \(a[5]\)開始，加2帶來的負作用解除了！
3、差分數組與原數組一樣長嗎？為什麼我看到了 b[r+1]=c,這樣差分不就多了一個元素嗎？
不是一樣長的，差分數組其實是比原數組多一個元素的，多的那個在數組的最後面。
當然，一般我們是不用到最後面的那個元素的，因為，差分的概念都是描述目前位置和前一個位置的差，字首和就是原數組了，最後一個生成的元素可以視為無效元素，沒有必要再糾結了。
4、C++ 代碼
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int a[N],b[N];
void insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),insert(i,i,a[i]);
while(m--){
int l,r,c;
scanf("%d%d%d",&l,&r,&c);
insert(l,r,c);
}
for(int i=1;i<=n;i++)b[i]+=b[i-1],printf("%d ",b[i]);
return 0;
}
5、二維差分概念
差分是字首和的逆運算。就是如果有一個二維的數組
b
b[1][1]+....+b[i][j]
,就是一個矩形範圍，它的最終加法結果值應該就是
a[i][j]
.就是原數組i,j的位置值。
6、二維差分有什麼用？
和一維差分的用途基本一緻，在一個二維矩陣中，有多塊區間需要增加或減少一個數值，多次操作後求最終的矩陣内容。如果按照傳統辦法，就是二層循環，複雜度很高，如果預處理出一個二維的差分矩陣，以後的多輪操作都轉為了4次加加減減操作，可以視為\(O(1)\)級别的時間複雜度，運算效率将得到極大提高。
7、看一下實際的例子
#include<iostream>
using namespace std;
const int N = 1010;
int a[N][N], b[N][N];
/**
測試用例:
原始數組
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
二維差分數組
1 1 1 1
4 0 0 0
4 0 0 0
4 0 0 0
*/
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() {
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
insert(i, j, i, j, a[i][j]);
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
printf("%d ", b[i][j]);
}
printf("\n");
}
return 0;
}
8、二維差分公式推導
\(① s[3][3] = b[1][1]+b[1][2]+b[1][3]\)
\(\ \ \ \ \ \ \ \ \ \ \ + b[2][1]+b[2][2]+b[2][3]\)
\(\ \ \ \ \ \ \ \ \ \ \ + b[3][1]+b[3][2]+b[3][3]\)
\(② s[2][3] = b[1][1]+b[1][2]+b[1][3]\)
\(③ s[3][2] = b[1][1]+b[1][2]\)
\(\ \ \ \ \ \ \ \ \ \ \ + b[2][1]+b[2][2]\)
\(\ \ \ \ \ \ \ \ \ \ \ + b[3][1]+b[3][2]\)
\(④ s[2][2] = b[1][1]+b[1][2]\)
\(①-②-③+④\)
\(b[3][3]=s[3][3]-s[2][3]-s[3][2]+s[2][2]\)
9、二維差分如何建構？
void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c; //開始位置增加C
b[x2 + 1][y1] -= c; //見上面的圖，把第二行的藍色區域減去C
b[x1][y2 + 1] -= c; //見上面的圖，把第一行的藍色區域減去C
b[x2 + 1][y2 + 1] += c; //交叉位置被減了兩次，需要補回來。
}
10、C++ 代碼
#include<iostream>
using namespace std;
const int N=1010;
int n,m,q;
int a[N][N],b[N][N];
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(){
scanf("%d%d%d",&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]);
while(q--){
int x1,y1,x2,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++)
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++)
printf("%d ",b[i][j]);
puts("");
}
return 0;
}