1.1 數(shù)組

數(shù)組是相同數(shù)據(jù)類型元素的集合所組成的一種數(shù)據(jù)結(jié)構(gòu)，數(shù)組在內(nèi)存中是連續(xù)的，它的大小在初始化的時(shí)候就已經(jīng)固定，數(shù)組一旦創(chuàng)建，它的長度是不能改變的，常見的動(dòng)態(tài)數(shù)組ArrayList并不是改變了數(shù)組的長度，而是又重新創(chuàng)建了一個(gè)數(shù)組。可以通過數(shù)組的下標(biāo)來修改數(shù)組，數(shù)組的下標(biāo)一般都是從0開始的，比如a[0]是數(shù)組的第一個(gè)元素，a[5]是數(shù)組的第6個(gè)元素等，如圖1-1所示。

最常見的數(shù)組是一維數(shù)組，它的定義如下（這里以Java為例）。除了一維數(shù)組還有二維數(shù)組、三維數(shù)組等，這里就不再過多介紹。

1.1.1 滾動(dòng)數(shù)組

滾動(dòng)數(shù)組也是使用數(shù)組來實(shí)現(xiàn)的，它不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種算法優(yōu)化思想，滾動(dòng)數(shù)組的作用在于優(yōu)化空間，讓數(shù)組滾動(dòng)起來，每次使用固定的幾個(gè)存儲(chǔ)空間，比如常見的斐波那契數(shù)列：f[n]=f[n-1]+f[n-2]，普通的寫法如下：

如圖1-2所示，雖然我們定義了一個(gè)很長的數(shù)組，但每次只用最近的3個(gè)，前面的都浪費(fèi)了，所以可以使用滾動(dòng)數(shù)組，只需要一個(gè)長度為3的數(shù)組即可。

上面講的是一維數(shù)組，對(duì)于二維數(shù)組有時(shí)候也可以使用滾動(dòng)數(shù)組。這需要結(jié)合具體的示例來講解，具體將在第11章動(dòng)態(tài)規(guī)劃中進(jìn)行介紹。

1.1.2 差分?jǐn)?shù)組

假設(shè)給定一個(gè)數(shù)組nums，先對(duì)區(qū)間[a,b]中的每個(gè)元素加3，再對(duì)區(qū)間[c,d]中的每個(gè)元素減5等，這樣非常頻繁的區(qū)間修改，常規(guī)的做法可以一個(gè)個(gè)計(jì)算，代碼如下：

頻繁對(duì)數(shù)組的一段區(qū)間增加或減去同一個(gè)值，如果一個(gè)個(gè)去操作，效率會(huì)很低，可以使用差分?jǐn)?shù)組，差分?jǐn)?shù)組就是原始數(shù)組相鄰元素之間的差。定義差分?jǐn)?shù)組d[n]，那么可以得到：d[i]=nums[i]-nums[i-1]，其中d[0]=nums[0]，如圖1-3所示。

可以看到原數(shù)組就是差分?jǐn)?shù)組的前綴和。

有了差分?jǐn)?shù)組，如果對(duì)區(qū)間[a,b]中的每個(gè)元素加3，就不需要再一個(gè)個(gè)操作，只需要在差分?jǐn)?shù)組的兩端進(jìn)行修改即可，如圖1-4所示。

1.1.3 二維差分?jǐn)?shù)組

我們可以把一維差分?jǐn)?shù)組看作是一條直線，只需要用后面的值減去前面的值，就可以構(gòu)造差分?jǐn)?shù)組。而二維差分?jǐn)?shù)可以把它看作是一個(gè)平面，如圖1-5所示，它的定義如下：

如果想獲取原數(shù)組，根據(jù)上面的公式可以得到：

如圖1-6所示，以（x1,y1）為左上角，（x2,y2）為右下角構(gòu)成一個(gè)區(qū)間，如果對(duì)這個(gè)區(qū)間內(nèi)的每個(gè)元素增加val，只需要執(zhí)行下面四步即可。

1.1.4 樹狀數(shù)組

假設(shè)有一個(gè)數(shù)組，對(duì)它進(jìn)行大量的修改和查詢，修改的是數(shù)組中某一個(gè)元素的值，查詢的是數(shù)組中任意一個(gè)區(qū)間的和。對(duì)于修改比較簡單，時(shí)間復(fù)雜度是O(1)，而查詢的時(shí)間復(fù)雜度是O(n)。大家可能會(huì)建議使用前綴和來優(yōu)化，前綴和查詢的時(shí)間復(fù)雜度確實(shí)是O(1)，但如果我們修改某一個(gè)元素的時(shí)候，前綴和后面的值也都要修改，時(shí)間復(fù)雜度是O(n)。那么有沒有一種方式可以讓修改和查詢時(shí)間復(fù)雜度降一個(gè)數(shù)量級(jí)呢？有的，那就是樹狀數(shù)組，它的修改和查詢時(shí)間復(fù)雜度都是O(logn)，綜合來看還是不錯(cuò)的。如圖1-7所示，這是一個(gè)樹狀數(shù)組，其中數(shù)組a[]是原始數(shù)組，數(shù)組c[]是樹狀數(shù)組。

令樹狀數(shù)組每個(gè)位置保存的是子節(jié)點(diǎn)值的和，則有：

通過上面的公式可以發(fā)現(xiàn)一個(gè)規(guī)律：

比如c[6]，6的二進(jìn)制是（110），最右邊有1個(gè)0，那么k就等于1，所以：

再比如c[4]，4的二進(jìn)制是（100），最右邊有2個(gè)連續(xù)的0，那么k就等于2，所以：

通過圖1-7可以發(fā)現(xiàn)，在樹狀數(shù)組c[i]中，如果i是奇數(shù)，c[i]就在第0層，也就是樹狀數(shù)組的葉子節(jié)點(diǎn)，并且c[i]=a[i]。如果i不是奇數(shù)，那么在i的二進(jìn)制位中，它的右邊有幾個(gè)0, c[i]就在第幾層。我們定義函數(shù)int lowBit (int x)表示只保留x的二進(jìn)制中最右邊的1，其他位置全部變?yōu)?，比如：

函數(shù)int lowBit (int x)的代碼如下：

這個(gè)很好理解，比如數(shù)字12和-12，它們的二進(jìn)制如下，只要對(duì)它們進(jìn)行&運(yùn)算，就是我們想要的結(jié)果。

我們令s[i]表示原始數(shù)組a的前i項(xiàng)和，通過圖1-7可以找出s和c的關(guān)系：

通過上面等式的關(guān)系可以得出規(guī)律：

這里的k1,k2,k3,……,kn都是2的k次方，實(shí)際上就是不斷地抹去i的二進(jìn)制中右邊的1，直到i變成0為止。比如數(shù)字7，它的二進(jìn)制是111，所以s[111]=c[111]+c[110]+c[100]（這里的數(shù)字是用二進(jìn)制表示），也就是s[7]=c[7]+c[6]+c[4]。

這個(gè)就是求和，如果我們想要計(jì)算數(shù)組區(qū)間[left,right]的和，可以像下面這樣調(diào)用。

樹狀數(shù)組的求和我們知道了，那么修改呢（這里先討論單點(diǎn)修改）。如果樹狀數(shù)組的一個(gè)節(jié)點(diǎn)值被修改了，那么它的父節(jié)點(diǎn)值都要改變，如圖1-8所示，當(dāng)a[5]的值被修改后，那么c5、c6以及c8都要修改。

如果要更改c[i]的值，只需要找到c[i]的父節(jié)點(diǎn)以及其父節(jié)點(diǎn)的父節(jié)點(diǎn)，一直往上走，直到根節(jié)點(diǎn)，全部修改即可。通過圖1-8可以發(fā)現(xiàn)，c[i]的父節(jié)點(diǎn)就是c[i+lowBit(i)]，所以需要以c[i]為起點(diǎn)，通過循環(huán)不斷地往上找父節(jié)點(diǎn)，然后修改，來看一下樹狀數(shù)組的完整代碼：

1. 區(qū)間更新，單點(diǎn)查詢

對(duì)于數(shù)組更新和查找可以分為下面幾類：

?單點(diǎn)更新，單點(diǎn)查詢。

?單點(diǎn)更新，區(qū)間查詢。

?區(qū)間更新，單點(diǎn)查詢。

?區(qū)間更新，區(qū)間查詢。

對(duì)于單點(diǎn)更新，單點(diǎn)查詢，原始數(shù)組就可以做，不需要構(gòu)建樹狀數(shù)組。而單點(diǎn)更新，區(qū)間查詢?cè)谇懊鎰倓偨榻B過，這里來看一下區(qū)間更新，單點(diǎn)查詢。如果想要區(qū)間更新，需要構(gòu)建差分?jǐn)?shù)組，在前面1.1.2小節(jié)差分?jǐn)?shù)組中講過，如果要更新原始數(shù)組區(qū)間的值，只需要更新差分?jǐn)?shù)組兩邊的值即可。其中差分?jǐn)?shù)組的前綴和就是數(shù)組a中某個(gè)元素的值，來看一下代碼：

2. 區(qū)間更新，區(qū)間查詢

區(qū)間更新可以使用差分?jǐn)?shù)組，那么區(qū)間查詢呢？假設(shè)求數(shù)組a的前n項(xiàng)和，來看一下公式推導(dǎo)，如圖1-9所示。

a是原數(shù)組，d是差分?jǐn)?shù)組，這里需要構(gòu)建兩個(gè)樹狀數(shù)組，其中d1[i]=d[i]，d2[i]=d[i]?(i-1)。

前面介紹的是一維樹狀數(shù)組，大家也可以研究一下二維樹狀數(shù)組，這里就不再介紹。區(qū)間更新和區(qū)間查詢除了使用樹狀數(shù)組，還可以使用線段樹，線段樹不光可以區(qū)間求和，還可以求區(qū)間最大值、區(qū)間最小值，功能要比樹狀數(shù)組更強(qiáng)大，關(guān)于線段樹會(huì)在1.6.6小節(jié)線段樹中介紹。