樹狀數組
- 樹狀數組的作用：計算一些資料的從1開始計算到 i i i位置的和、從1位置到 i i i位置的最大值，等。這些運算都必須滿足有聚合運算的性質，（滿足結合律）。例如，對于求最大值，定義 a ( M ) b a (M) b a(M)b為求 a a a與 b b b的最大值，與加法的結合律相同，由結合律存在下式：
[ a ( M ) b ] ( M ) c = a ( M ) [ b ( M ) c ] [a(M)b](M)c=a(M)[b(M)c] [a(M)b](M)c=a(M)[b(M)c]
- 樹狀數組是一種資料結構。對于：
a 1 , a 2 , a 3 , . . . , a n a_1, a_2, a_3, ... ,a_n a1,a2,a3,...,an
- 若将其使用樹狀數組，則會有 ≤ log n \leq \log n ≤logn個攤（分組）。
- 對攤的定義與解釋：
- 舉一個簡單的例子：将7寫成二進制：
21 = ( 10101 ) 2 = 1 ∗ 2 4 + 1 ∗ 2 2 + 1 21 = (10101)_2 = 1*2^4 + 1*2^2 + 1 21=(10101)2=1∗24+1∗22+1
- 7可分為 （前4）+（中2）+（後1）。
- 現在對于 a 1 … a 21 a_1…a_{21} a1…a21來說，可以通過同樣的編碼方法将其分組：
a 1 + . . . a 21 = ( a 1 + . . . + a 16 ) + ( a 17 + . . . + a 20 ) + ( a 21 ) a_1 + ...a_{21} = (a_1 + ...+a_{16}) + (a_{17} + ...+a_{20}) + (a_{21}) a1+...a21=(a1+...+a16)+(a17+...+a20)+(a21)
T 1 : a 1 → a 1 T 2 : a 1 → a 2 T 3 : a 3 → a 3 T 4 : a 1 → a 4 T 5 : a 5 → a 5 T 6 : a 5 → a 6 T 7 : a 7 → a 7 T 8 : a 1 → a 8 T_1: a_1 \rightarrow a_1 \\ T_2: a_1 \rightarrow a_2 \\ T_3: a_3 \rightarrow a_3 \\ T_4: a_1 \rightarrow a_4 \\ T_5: a_5 \rightarrow a_5 \\ T_6: a_5 \rightarrow a_6 \\ T_7: a_7 \rightarrow a_7 \\ T_8: a_1 \rightarrow a_8 T1:a1→a1T2:a1→a2T3:a3→a3T4:a1→a4T5:a5→a5T6:a5→a6T7:a7→a7T8:a1→a8
- 例如，對于 a 1 , … , a 64 a_1, … , a_{64} a1,…,a64而言，：
- 長度為64的隻有一堆：[1, 64]；
- 長度為32的有2，1堆：[1, 32]，[33,64]；
- 長度為16的有4，2堆：[1, 16]，[17, 32]，[33, 48]，[49, 64]；
-
長度為8的有8，4堆：[1, 8]，[9, 16]，[17, 24]，[25, 32]，[33, 40]，[41, 48]，[49, 56]，[57, 64]；
……等。
- 對于末尾重複的區間，删去較小的區間，保留較大的區間，以做到節省的目的。在上面的例子當中，可以發現：區間最末尾的值 0 < t i ≤ n 0<t_i\leq n 0<ti≤n，出現且僅出現一次，是以可以發現，總共存在 n n n個區間，是以有 ≤ log n \leq \log n ≤logn個分組
20190509：學校-3-樹狀數組 - 在上面的例子當中，每個攤所管的數量可以得到規律：對于每個 T [ i ] T[i] T[i]，其所管的長度為 l b ( i ) lb(i) lb(i)
- 上面的 l b ( i ) lb(i) lb(i)為“low bit”，為在二進制數當中的最後一個出現的 1 1 1所代表的十進制數，例如：對于12而言， 12 = ( 1100 ) 2 12 = (1100)_2 12=(1100)2，則最後一個 1 1 1為 ( 100 ) 2 = 4 (100)_2 = 4 (100)2=4，則 l b ( 12 ) = 4 lb(12)=4 lb(12)=4。是以 T [ 12 ] T[12] T[12]所管理的區間為 [ 9 , 12 ] [9, 12] [9,12]。
- 同樣地，可以總結出：對于每一個 S [ i ] S[i] S[i]，所管的區間為： [ i − l b ( i ) + 1 , i ] [i - lb(i) + 1, i] [i−lb(i)+1,i]。
- 在樹狀數組當中，計算的時候，采用上述的攤的計算方式。由此結束了計算的時候的解釋。
- 綜合上面的叙述可以不難發現：對于 a 1 , a 2 , a 3 , … , a n a_1, a_2, a_3, … ,a_n a1,a2,a3,…,an而言，一共會定義 n n n個數組， T [ n ] T[n] T[n]，但是在運算的時候，會根據實際的需要，選取相關分組的運算，使得時間複雜度為 O ( log n ) O(\log n) O(logn)。
- 首先，必需要對數組進行初始化（共有 ≤ log n \leq \log n ≤logn個分組）：初始化成為目标運算的值，例如加法即為和，求最大值即為各數組的最大值。例如：
這就是當新的值被添加進來的情況，這等價于将第 i i i号為的值由 0 0 0改為 a i a_i ai，時間複雜度為 log N \log N logN。for (int i = 1; i <= n; i ++) { cin >> a[i]; add(i, a[i]); }
- 對數組進行求和的操作
- 對數組進行修改： a d d ( i , Δ ) ⇒ a i → a i + Δ add(i, \Delta) \Rightarrow a_i \rightarrow a_i + \Delta add(i,Δ)⇒ai→ai+Δ：
- 研究對數組進行改動，必須研究改動所帶來的牽連影響，研究對 a i a_i ai資料的改動，将影響那些區間的運算結果。
-
再舉個簡單的例子：若對于數組的第九個元素進行改動，則：
[ 9 , 9 ] → t [ 9 ] → 9 [ 9 , 10 ] → t [ 10 ] → 9 + l b ( 9 ) = 10 [ 9 , 12 ] → t [ 12 ] → 10 + l b ( 10 ) = 12 [ 1 , 16 ] → t [ 16 ] → 12 + l b ( 12 ) = 16 [9, 9] \rightarrow t[9] \rightarrow 9 \\ [9, 10] \rightarrow t[10] \rightarrow 9 + lb(9) = 10 \\ [9, 12] \rightarrow t[12] \rightarrow 10 + lb(10) = 12 \\ [1, 16] \rightarrow t[16] \rightarrow 12 + lb(12) = 16 [9,9]→t[9]→9[9,10]→t[10]→9+lb(9)=10[9,12]→t[12]→10+lb(10)=12[1,16]→t[16]→12+lb(12)=16
- 在這個例子當中，會發現上述的區間都會影響，歸納為 t i ’ = t i + l b ( i ) t_i’ = t_i + lb(i) ti’=ti+lb(i)。
- 可以寫成以下代碼：
void add(int i, int d) { while (i <= n) { T[i] += d; i += lb(i); } } - 對數組進行查詢第 1 − j 1-j 1−j個元素之和： s u m ( j ) ⇒ a 1 + a 2 + … + a j sum(j) \Rightarrow a_1 + a_2 + … + a_j sum(j)⇒a1+a2+…+aj：
-
再舉一個簡單的例子：求前23個元素的和：
ans + = T [ 23 ] → [ 23 , 23 ] → 23 ans + = T [ 22 ] → [ 21 , 22 ] → 23 − l b ( 23 ) = 22 ans + = T [ 20 ] → [ 16 , 20 ] → 22 − l b ( 22 ) = 20 ans + = T [ 16 ] → [ 1 , 16 ] → 20 − l b ( 20 ) = 16 16 − l b ( 16 ) = 0 \text{ans} += T[23] \rightarrow [23, 23] \rightarrow 23 \\ \text{ans} += T[22] \rightarrow [21, 22] \rightarrow 23 - lb(23) = 22 \\ \text{ans} += T[20] \rightarrow [16, 20] \rightarrow 22 - lb(22) = 20 \\ \text{ans} += T[16] \rightarrow [1, 16] \rightarrow 20 - lb(20) = 16 \hspace{5pt} \\ 16 - lb(16) = 0 ans+=T[23]→[23,23]→23ans+=T[22]→[21,22]→23−lb(23)=22ans+=T[20]→[16,20]→22−lb(22)=20ans+=T[16]→[1,16]→20−lb(20)=1616−lb(16)=0
- 将上述規律歸納成代碼：
int sum(int i) { int ans = 0; while (i > 0) { ans += T[i]; i -= lb(i); } return ans; } -
- 對數組進行最大值的操作：
-
對數組進行修改： a d d ( i , Δ ) ⇒ a i → a i + Δ ⇒ T [ m … n ] = max { T [ m … n ] , a [ i ] + Δ } add(i, \Delta) \Rightarrow a_i \rightarrow a_i + \Delta \Rightarrow T[m…n] = \max\{T[m…n] , a[i] + \Delta\} add(i,Δ)⇒ai→ai+Δ⇒T[m…n]=max{T[m…n],a[i]+Δ}
同理：
void add(int i, int d) { while (i <= n) { T[i] = max(T[i], a[i] + d); i += lb(i); } } -
對數組進行計算取最值： m a x ( j ) ⇒ max { a 1 , a 2 , a 3 , … , a j } max(j) \Rightarrow \max\{a_1, a_2, a_3, …, a_j\} max(j)⇒max{a1,a2,a3,…,aj}
同理：
int max(int i) { int ans = 0; while (i > 0) { ans = max(ans, T[i]); i -= lb(i); } }
- 再論 l b ( i ) lb(i) lb(i)：
- 由于 l b ( i ) lb(i) lb(i)為 i i i轉換為二進制後的自後向前數到的第一個 1 1 1和若幹個 0 0 0的十進制表示，是以便可以将 l b ( i ) lb(i) lb(i)的計算成 l b ( i ) = i & ( − i ) lb(i) = i\hspace{5pt} \& \hspace{5pt}(-i) lb(i)=i&(−i)。
- 對于 − i -i −i，計算機會對其進行取反加一的操作（負數以其正值得補碼形式表達）。
- 例如對于 ( 011011000 ) 2 (011011000)_2 (011011000)2取反： ( 100100111 ) 2 (100100111)_2 (100100111)2，再加一得到 ( 100101000 ) 2 (100101000)_2 (100101000)2。
- 此時的（位運算） i i i與 − i -i −i的與就是 l b ( i ) lb(i) lb(i)的值。
-
例子：
( 011011000 ) 2 & ( 100101000 ) 2 − − − − − − − − − − ( 000001000 ) 2 = 8 \hspace{5pt}\hspace{5pt}(011011000)_2 \\ \&\hspace{5pt}(100101000)_2 \\ ----------\\ \hspace{5pt}\hspace{5pt}\hspace{5pt}\hspace{5pt}\hspace{5pt}\hspace{5pt}(000001000)_2 = 8 (011011000)2&(100101000)2−−−−−−−−−−(000001000)2=8
則 l b ( 216 ) = l b [ ( 011011000 ) 2 ] = 8 lb(216) = lb[(011011000)_2] = 8 lb(216)=lb[(011011000)2]=8
int lb(int i) { return i & (-i); }正因為這個特性：可以将某一個二進制數表達為： … 10 … 0 ( n zeros ) …10…0(n \text{ zeros}) …10…0(n zeros)。
則其的相反數即為： … 01 … 1 ( n ones ) + 1 = … 10 … 0 ( n zeros ) …01…1(n\text{ ones}) + 1 = …10…0(n\text{ zeros}) …01…1(n ones)+1=…10…0(n zeros)。将兩數取與，則在第 1 − n 1-n 1−n為皆為 0 & 1 = 0 0 \& 1 = 0 0&1=0，在第 n + 1 n+1 n+1位為 1 & 1 = 1 1\&1 = 1 1&1=1，其後也皆為 0 0 0。（此處的位數順序為自後向前）
- 綜上所述，可以發現：使用樹狀數組，無論是添加元素，修改元素，還是查詢某位置的結果，其事件複雜度均相同，為 log n \log n logn。
![【資料結構】 醫院選址[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)