1.2　樹狀數組

樹狀數組（Binary Indexed Tree，BIT）能夠高效地求序列區間和。樹狀數組的實現簡單，巧妙地運用了二進制的思想。

1.2.1　樹狀數組的定義

給定一個數組進行兩個操作：一是更新某點的值；二是求某段區間的和。對于普通的數組，單點更新的復雜度為O（1），求區間和的復雜度為O（n），而樹狀數組能夠把單點更新和區間求和的復雜度都變為O（nlogn）。

設數組A[]為原數組，定義C[i]=A[i-2k+1]+…+A[i]。其中，k為i用二進制表示時的末尾0的個數，如C[1]=A[1]，C[2]=A[1]+A[2]，C[3]=A[3]，C[4]=A[1]+A[2]+A[3]+A[4]，…。也就是說，C[i]就是從A[i]開始前2k項的和，如圖1.3所示。

1.2.2　樹狀數組的實現和使用

k為x用二進制表示時末尾0的個數，對于2k，有一種快速的求解方法：

當修改某一點的值時，只需要修改某一點的所有父節點就可以了。對于一個節點i來說，它的父節點的編號為i+lowbit（i）。因此對于單點修改的函數為

前n個數的和記為sum（n），已知C[i]是從i開始向前lowbit（i）個數的和，所以sum（n）=C[n]+sum[n-lowbit（n）]。

區間[start,end]的區間和可以通過sum（end）-sum（start）來求得。樹狀數組也可以進行區間增減更新和單點查詢操作。A[]是原數組，構造差分數組D[]，令D[1]=A[1]，D[i]=A[i]-A[i-1]（i>1），則數組A是數組D的前綴和，即A[i]=D[1]+D[2]+…+D[i]。這樣求A的單點值就是求D的區間和。更新A某段區間[start,end]的值只需要更改D[start]和D[end+1]的值就可以了。這兩個操作可以通過構造D的樹狀數組求得。

1.2.3　例題講解

例1-1　Sort it

Time Limit:2000/1000 ms（Java/Others）　Memory Limit:32768/32768 KB（Java/Others）

題目描述：

給定一個由n個不同的整數組成的序列，通過交換相鄰的兩個數，使得序列變成上升的。問最少需要交換多少次，如“1 2 3 5 4”，需要進行一次操作，交換5和4。

輸入：

輸入包含多組數據，每一組數據包含兩行，第一行為一個正整數n（n≤1000），第二行為從1到n的n個整數的一個序列。

輸出：

輸出為1行，輸出最少需要交換的次數。

樣例輸入：

3

1 2 3

4

4 3 2 1

樣例輸出：

0

6

題目來源：HDOJ 2689。

解題思路：

題目可以轉化成求數組中逆序對的數量。

逆序對：設數組A為一個有n個數字的有序集（n>1），其中的數字均不相同，如果存在正整數i，j，使得1≤i<j≤n而且A[i]>A[j]，則<A[i],A[j]>這個有序對稱為A的一個逆序對。

對于每一個數字，求它前面有多少個數字大于它，即該數字的貢獻，所有數字的貢獻和即逆序對的數量。對于A[i]=x，在樹狀數組的x處加1，然后求sum（x）就是在x前面有多少個數小于等于x，那么i-sum（x）就是A[i]的貢獻。從左到右對于每一個數邊插入邊求和。

題目實現：