【編程筆記】差分·差分矩陣
差分，即前綴和的逆運算，兩者之間的關(guān)系類似于數(shù)學(xué)中的求導(dǎo)和積分的關(guān)系。
差分（一維差分）
輸入一個長度為 n 的整數(shù)序列。
接下來輸入 m 個操作，每個操作包含三個整數(shù) l,r,c，表示將序列中 [l,r] 之間的每個數(shù)加上 c。
輸出進(jìn)行完所有操作后的序列。
輸入格式
第一行包含兩個整數(shù) n 和 m。
第二行包含 n 個整數(shù)，表示整數(shù)序列。
接下來 m 行，每行包含三個整數(shù) l，r，c，表示一個操作。
輸出格式
共一行，包含 n 個整數(shù)，表示最終序列。
差分思路
現(xiàn)有前綴和數(shù)組：
a[1], a[2], a[3], ... , a[n]
那么構(gòu)造差分?jǐn)?shù)組：
b[1], b[2], b[3], ... , b[n]
且使得
a[1]= b[1]
a[2]= b[1]+b[2]
a[3]= b[1]+b[2]+b[3]
...
a[i]= b[1]+b[2]+...+b[i]
對一般用來快速操作整個數(shù)組，比如把c加到一個數(shù)組的[l，r]部分的所有數(shù)據(jù)上。相較于時間復(fù)雜度至少為O(n)的暴力方法，差分算法可以將時間復(fù)雜度降低到O(1)。
對于[l, r]+c的情況，先用前綴和的思路去考慮一下。
假如現(xiàn)b[l]加上c變成b[l]+c, 那么
a[l]也會自動加上c(a數(shù)組是b數(shù)組的前綴和)，且a[l]及之后的數(shù)組都會加上c。
[l, n]+c情況基本如下
差分?jǐn)?shù)組：b[1], b[2], b[l]+c, ... , b[n]
前綴和數(shù)組：a[1], a[2], a[l]+c, ... , a[n-1]+c, a[n]+c
由于實際的需求是[l,r]
所以需要把r之后的數(shù)全部減去c
即在b數(shù)組的r+1之后的數(shù)全部減c
如此一來
差分?jǐn)?shù)組：b[1], b[2], b[l]+c, ... ,b[r], b[r+1]-c, ..., b[n-1],b[n]
前綴和數(shù)組：a[1], a[2], a[l]+c, ... , a[r]+c, a[r+1], ...,a[n-1], a[n]
差分過程
構(gòu)建差分?jǐn)?shù)組
區(qū)間[l, r]范圍內(nèi)加上需要的c
前綴和運算
insert就是在實現(xiàn)差分。
此外，特別強(qiáng)調(diào)：
b[i]+=b[i-1]
由于需要“輸出最終整數(shù)序列”，所以需要進(jìn)行前綴和操作，使b[i][j]變成新的a[i][j]。
而這條怎么來的呢？
在一維前綴和中，可知
S[i]=S[i-1]+a[i]?
而在這里，S[i][j]就是新的b[i][j]，a[i][j]就是原來的b[i][j]
差分矩陣（二維差分）
輸入一個 n 行 m 列的整數(shù)矩陣，再輸入 q 個操作，每個操作包含五個整數(shù) x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一個子矩陣的左上角坐標(biāo)和右下角坐標(biāo)。
每個操作都要將選中的子矩陣中的每個元素的值加上 c。
將進(jìn)行完所有操作后的矩陣輸出。
輸入格式
第一行包含整數(shù) n,m,q。
接下來 n 行，每行包含 m 個整數(shù)，表示整數(shù)矩陣。
接下來 q 行，每行包含 5 個整數(shù) x1,y1,x2,y2,c，表示一個操作。
輸出格式
共 n 行，每行 m 個整數(shù)，表示所有操作進(jìn)行完畢后的最終矩陣。
差分矩陣的思路
與前綴和矩陣相同，差分矩陣同樣用到了“容斥原理”的思想，即先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去，使得計算的結(jié)果既無遺漏又無重復(fù)。
假設(shè)需要給（x1,y1）(x2,y2)的子矩陣中的數(shù)全部加上c。, , ,?
?那么b[x1][y1]+c就會使如下藍(lán)色部分全部加c。（大于等于x1,y1的部分分別加c）
同理，范圍過大，還需要刪除不必要的部分，即減去c。
在刪除多余部分的時候，基于容斥原理，還要重新補(bǔ)充重復(fù)刪除的部分
差分矩陣過程
構(gòu)建差分?jǐn)?shù)組
在矩陣（x1,y1)(x2, y2)范圍內(nèi)加上需要的c
前綴和運算
puts()函數(shù)的作用與語句printf("%s\n",s)的作用相同
此外，特別強(qiáng)調(diào)：
b[i][j]+=b[i-1]b[j]+b[i][j-1]-b[i-1][j-1]
由于需要“將進(jìn)行完所有操作后的矩陣輸出”，所以需要進(jìn)行前綴和操作，使b[i][j]變成新的a[i][j]。
而這條怎么來的呢？
在二維前綴和中，可知
S[i,j]=S[i,j?1]+S[i?1,j]?S[i?1,j?1]+a[i,j]?
而在這里，S[i][j]就是新的b[i][j]，a[i][j]就是原來的b[i][j]
總結(jié)，對于差分，只用考慮如何更新而非考慮如何構(gòu)造。
