檢視樹狀陣列的原始碼

'''樹狀陣列'''抑是'''二箍索引樹仔'''（英語：Binary Indexed Tree）， 閣以其發明者號名做 Fenwick 樹，上早由 Peter M . Fenwick 佇咧一九九四年以 A New Data Structure for Cumulative Frequency Tables 為題發表佇咧 SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決資料壓縮內底的累積頻率（Cumulative Frequency）的計算問題，現多用佇高效計算數列的字首和，區間佮。伊會當 $ O ( \ log n ) $ 的時間得著任意字首和 $ \ sum _ { i=一 } ^ { j } A [i] , 一 <=j <=N $，並同時支援佇咧 $ O ( \ log n ) $ 時間內支援動態單點值的修改。空間複雜度 $ O ( n ) $。

==結構起源==

照起來 Peter M . Fenwick 的講法，正如所有的整數攏會當表示做二的冪佮，咱嘛會當共一順序列表示做一系列囝序列的佮。所以採用這个想法，阮會當將一个字首和劃分做真濟字序列的和，咧畫分的方法佮數的二的冪佮具有極其相𫝛的方式。一方面，子序列的個數是其二進位表示中一的個數，另外一方面，子序列代表的 f [i] 的個數嘛是二的冪。

==基本操作==

===ió-bih 函式===

定義一个 ` lowbit ` 函式，轉去參數轉做二進位了後，上尾一个一的位置所代表的數值。

比如講，` lowbit ( 三十四 ) ` 的倒轉去值將是二；而且 ` lowbit ( 十二 ) ` 返回四；` lowbit ( 八 ) ` 返回八。

共三十四轉做二進位 ( 十十 ) 二。遮的「上尾仔一个一」是對 $ 二 ^ { 零 } $ 位前數，見著的頭一个一，也就是講 $ 二 ^ { 一 } $ 位頂的一。

程式上，` ( ~ i + 一 ) & i ` 表明矣上尾仔一个一的值。

猶原以三十四為例，~ ( 十十 ) 的結果是一千一百空一一千一百空一（二百二十一）， 加一後為一千一百空一一千一百十（兩百二十二）， 十十佮一千一百空一一千一百十作 AND，得零十（二）。

` lowbit ` 的一个簡便求法 :（C + +）

===新起===

定義一个陣列 BIT，共維護 $ A $ 的字首和，著：$ BIT _ { i }=\ sum _ { j=i-lowbit ( i ) + 一 } ^ { i } A _ { j } $

具體能用下跤式實現：（C + +）

===修改===

假使講這馬欲將 $ A [i] $ 的值增加 delta，

遐爾，攏愛共這 $ BIT [i] $ 崁的區間包含 $ A [i] $ 的值攏加上 delta，

這个過程會當寫做遞迴，抑是普通的迴箍。

需要計算的次數佮資料規模 N 的位元數有關，即這部份的時間複雜度是 $ O ( \ log { N } ) $。

會當修改函式的 C + + 寫法：

===求和===

準講咱需要計算 $ \ sum _ { i=一 } ^ { k } A _ { i } $ 的值。

一 . 首先，將 ans 初初化做零，將 i 初初化為 k。
二 . 將 ans 的值加上 ` BIT [i] `。
三 . 將 i 的值減去 ` lowbit ( i ) `。
四 . 重複步數字～三，一直到 i 的值變做零。

求和函式的 C / C + + 寫法：

===時空複雜度===

* 初初化複雜度做好的為：$ O ( N ) $
* 單次詢問複雜度：$ O ( \ log N ) $，其中 N 為陣列大細
* 單改修改複雜度：$ O ( \ log N ) $，其中 N 為陣列大細
* 空間複雜度：$ O ( N ) $

==應用==

===求逆序嘿數===

逆序嘿數是一个數列中佇咧伊頭前有比伊較大的個數乎。如四千三百十二的逆序嘿數是零 + 一 + 二 + 二=五。

會當先共數列中的數揤大細順序轉化做 $ 一 $ 到 $ n $ 的整數，予原數列做一个 $ 一 , 二 , . . . , n $ 的排列 $ P $，建立一个樹狀陣列，用來記錄按呢一个陣列 $ A $（下標對做伙算起）的字首和：若排列中間的數 $ i $ 當前已經出現，著 $ A [i] $ 的值為 $ 一 $，抑無來做 $ 零 $。初初的時陣列 $ A $ 的值均為 $ 零 $，佇排列中的最後一个數開始遍歷，見擺佇樹狀內底查詢有偌濟支數小於當前的數 $ P [j] $（才用樹仔的陣列查詢陣列 $ A $ 目前 $ P [j] 影一 $ 個數的字條佮）閣加入計數器，以後對樹仔狀陣列執行修改陣列 $ A $ 第 $ P [j] $ 個數值加 $ 一 $ 的操作。

==參考文獻==

[[分類: 待校正]]