樹狀數組

樹狀數組或二叉索引樹（英語：Binary Indexed Tree），又以其發明者命名為Fenwick樹，最早由Peter M. Fenwick於1994年以A New Data Structure for Cumulative Frequency Tables為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裏的累積頻率（Cumulative Frequency）的計算問題，現多用於高效計算數列的前綴和， 區間和。 ^[1] 

按照Peter M. Fenwick的説法，正如所有的整數都可以表示成2的冪和，我們也可以把一串序列表示成一系列子序列的和。採用這個想法，我們可將一個前綴和劃分成多個子序列的和，而劃分的方法與數的2的冪和具有極其相似的方式。一方面，子序列的個數是其二進制表示中1的個數，另一方面，子序列代表的f[i]的個數也是2的冪。 ^[1] 

定義一個Lowbit函數，返回參數轉為二進制後,最後一個1的位置所代表的數值.

例如,Lowbit(34)的返回值將是2；而Lowbit(12)返回4；Lowbit(8)返回8。

將34轉為二進制,為0010 0010,這裏的"最後一個1"指的是從

位往前數,見到的第一個1,也就是

位上的1.

程序上，((Not I)+1) And I表明了最後一位1的值,

仍然以34為例,Not 0010 0010的結果是 1101 1101(221),加一後為 1101 1110(222), 把 0010 0010與1101 1110作AND,得0000 0010(2)。 ^[1] 

逆序數是一個數列中在它前面有比它大的個數。如4312的逆序數是0+1+2+2=5。

從最後一個數開始遍歷，每次在樹狀數組中查詢有多少個數小於當前的數並加入計數器，之後把當前元素加入樹狀數組。 ^[1]