前綴和與差分是兩個(gè)簡(jiǎn)單且實(shí)用的技巧，可以降低對(duì)序列的操作的復(fù)雜度，今天就來學(xué)習(xí)一下它們

前綴和

前綴和已經(jīng)在?貪心算法一本通平臺(tái)詳解?中 P1224：最大子矩陣 中提到過了

前綴和可以利用? 的時(shí)間處理數(shù)據(jù)，完成后每次詢問僅需? 的時(shí)間復(fù)雜度求解任意區(qū)間內(nèi)的和，相比之下，要比暴力求解長(zhǎng)度為? 的區(qū)間和 (??)?快得多

下面規(guī)定??為前綴和數(shù)組，?為原數(shù)組，?為指定求和的區(qū)間左右端

一維前綴和

前綴和最重要的就是前綴和數(shù)數(shù)組 ， 記錄著??到? 的和，但是我們需要的是?的值，那應(yīng)該如何做呢

相比之下，不難發(fā)現(xiàn)當(dāng)? 時(shí)，?中記錄的值多了? 這一部分，而一段的和也是能夠通過前綴和求出的，所以

前綴和很巧妙地將任意一段區(qū)間的和轉(zhuǎn)換為了兩段區(qū)間的和的差，從而大大降低了時(shí)間復(fù)雜度

如圖示中，1 操作中綠色的區(qū)間就是從 1~R 的和，2 操作中紅色的區(qū)間就是從 1~L-1 的和，3 操作中將紅色部分從綠色部分減去，最終就剩下了區(qū)間 L~R

在計(jì)算時(shí)并不需要對(duì)于每一個(gè)? 都重新從? 開始計(jì)算區(qū)間和，可以通過上一個(gè)區(qū)間和加上本次的值得到對(duì)應(yīng)的區(qū)間和

一維前綴和完全沒有什么難度，所以就會(huì)有一些弊端，如??可能會(huì)超出整型甚至是長(zhǎng)整型的范圍

二維前綴和

相比于一維前綴和，二維前綴和更加復(fù)雜，但是其原理仍然相同

同樣的，給出兩個(gè)位置? 和?，要求出兩點(diǎn)所圈起來的矩形中包含的所有元素的和，如下圖求綠色區(qū)域的和

根據(jù)一維差分不難想到，?記錄的應(yīng)該是，但是這次就不能像一維前綴和一樣簡(jiǎn)單的加減來求出某個(gè)區(qū)域內(nèi)的和了

下面將矩形ACBD區(qū)域內(nèi)的和記作?，其他矩形亦然

觀察上圖，不難發(fā)現(xiàn)下面的式子

可是其中除了??和??以外其他還需要繼續(xù)分解，將其繼續(xù)分解得到

合并后得到

注意到式子右側(cè)的字母都是以? 開頭的，說明其可以通過前綴和求得

形象地表達(dá)就是將 藍(lán)色+紅色+橙色+綠色?的部分減去 藍(lán)色+紅色 部分再減去 藍(lán)色+橙色 部分最后再加上 藍(lán)色 部分，其中每一個(gè)部分都可以通過前綴和數(shù)組? 直接訪問，所以

同樣地，在計(jì)算時(shí)也可以通過已計(jì)算出的數(shù)據(jù)來計(jì)算新的位置的值，因?yàn)榘凑諒淖蟮接遥瑥纳系叫〉捻樞蜻M(jìn)行計(jì)算，所以可以保證上方和左方是有正確的數(shù)據(jù)的，所以根據(jù)上面的公式，可以得到計(jì)算???區(qū)域的公式

差分

前綴和?( 一維?)?是利用??和? 來求取?的算法

那反過來，要將區(qū)間 到? 的所有元素都加上?，能不能也是用? 和? 來解決呢

既然前綴和是先預(yù)處理就能夠非常方便地求出區(qū)間和，那差分就先修改標(biāo)記 ( 標(biāo)記標(biāo)在差分?jǐn)?shù)組? 上?)，最后再來處理和

下面規(guī)定 ?為差分?jǐn)?shù)組，?和??為修改范圍，?為修改值

于是我們可以這樣進(jìn)行操作，在需要修改的區(qū)間的頭和尾分別打上標(biāo)記??和? 的標(biāo)記，即將? 加上?，將??減去

在最后處理的過程中，設(shè)置一個(gè)偏差值?，初始值為 ，表示接下來的數(shù)據(jù)沒有任何偏差，如果遇上差分標(biāo)記時(shí)，更改偏差值，表示接下來的標(biāo)記有著? 的偏差

但是看了下面的代碼你就會(huì)發(fā)現(xiàn)事實(shí)上我們并沒有設(shè)置偏差值?

我們將偏差值??存入了原數(shù)組??中，并通過依次繼承，讓偏差值一直存在于原數(shù)組??中，所以就無需設(shè)置專門的偏差值??了

好了，那么這篇文章就講到這里了，如果你覺得本文對(duì)你有所幫助，請(qǐng)不要忘記三連支持！