還記得我們在《歸并排序隻能用來排序？？？》中做過的尋找逆序對個數的問題嗎？除了使用歸并排序來解決外，使用樹狀數組也是一種可行的方式。接下來我們将詳細介紹這種簡潔優美的資料結構。
1 什麼是樹狀數組
首先，我們需要了解什麼是樹狀數組以及它用來解決哪種問題。
樹狀數組(Binary Index Tree)
也稱二叉索引樹，一般來說，樹狀數組支援與線段樹相同的兩種操作，單點修改和區間查詢，時間複雜度均為
O(logN)
:
- 單點修改：更改數組中一個元素的值
- 區間查詢：查詢一個區間内所有元素的聚集資訊(如總和、最值、平均值等)
那麼，它與線段樹究竟有什麼差別呢？
2 樹狀數組的實作
樹狀數組實際上是一個一維數組，在設計上，它采用了類似于線段樹的思想：每個元素代表一個小區間的和，單點更新時，隻更新包含這個元素的區間，在區間查詢時，将對應的小區間進行組合進而得到大區間的和。那麼這個小區間是如何确定的呢？
樹狀數組巧妙的利用了二進制運算，舉個例子，11的二進制形式為
1011
，如果我們要求前11個元素和，可以将其分為
0000-1000
，
1000-1010
，
1010-1011
三個小區間，分别求出它們的和後再相加即為前11個元素的和。實際上，類似
1000-1010
這種小區間的和正是樹狀數組的元素所代表的。可能有的人已經看出規律了，這不就是不斷去掉二進制右側1的過程嗎？
此時我們不得不介紹一個lowbit函數，它的作用是隻保留二進制最右邊的1，這個函數的實作如下：
public static int lowbit(int x) {
return x & (-x);
}
如6 = 00000110和-6 = 11111010 相與為 00000010
雖然有點匪夷所思，但x & (-x)确實能夠實作這個功能，大家可以用筆來算一算，這屬于經典的二進制位運算技巧，類似的還有x & (x-1)可以将二進制的最後一位1置為0，位運算的相關内容會在後續文章中介紹。
是以，介紹到這裡，我們應該能自己畫一下樹狀數組的結構圖了，假設數組的最後索引為8，所建構的樹狀數組如下：
在上面的介紹中我們可以了解到，樹狀數組的查詢是不斷查詢
(x-lowbit(x), x]
區間的和并把它們求和得到前n個元素的和，代碼實作如下：
public int query(int x) {
int ret = 0;
while (x != 0) {
ret += tree[x];
x -= lowbit(x);
}
return ret;
}
那麼樹狀數組如何進行更新操作呢，我們知道，單點更新後需要更新所有包含此元素的區間和，對于特定元素如100110，我們可以找到包含它的區間：
可以看出，樹狀數組每次進行更新時，會把右邊起連續的1變為0，再把這一系列1的前一位0變為1，這實際上可以看作一個不斷進位的過程，每一次所加的數正是lowbit(x)。代碼實作如下：
public void update(int x, int d) {
while (x <= n) {
tree[x] += d;
x += lowbit(x);
}
}
3 用樹狀數組解決逆序對問題
我們假設數組中所有元素均在1-10之間，使用一個桶數組來表示原始數組每一個元素出現的次數，如對于原數組a = {4, 5, 2, 3, 6}，其桶數組表示如下：
index -> 1 2 3 4 5 6 7 8 9
value -> 0 1 1 1 1 1 0 0 0
是以，我們可以采用這種方法來求數組的逆序對：反向周遊數組，對周遊到的元素ai，我們把對應的桶自增1，并将i-1位置的字首和加入到逆序對總數中。為什麼這樣能夠計算逆序對？試想，對于某個元素ai，其i-1位置的字首和表示的意義是小于ai的所有元素的個數，而這些元素在ai之前進入桶數組，因為我們是從後向前周遊的，是以這些元素在原序列中的位置在ai之後，再加上這些元素比ai小，是以ai與它們構成了逆序對。
以a數組為例，我們未添加元素5時，桶數組的情況如下：
index -> 1 2 3 4 5 6 7 8 9
value -> 0 1 1 0 0 1 0 0 0
在添加5後，我們計算桶數組前4項的和為2，可以清楚的看到，這兩個逆序對代表的是(5,2)和(5,3)。
設數組中元素的值域為size，當元素較為分散時，我們需要開辟的桶空間也會更大，而這個桶數組中很多位置的元素為0，實際上，在逆序對問題中，我們
并不關注元素的實際大小，而是關注它們的相對大小
，隻需要知道哪些數比哪些數大還是小，這就足夠了，是以為了節約不必要的空間開銷，我們可以對數組元素進行離散化處理。全部代碼如下：
class Solution {
public int reversePairs(int[] nums) {
Set set = new TreeSet<>();for(int num : nums) set.add(num);int idx = 1;int n = set.size();
Map map = new HashMap<>();for(int num : set){
map.put(num, idx++);
}
BIT bit = new BIT(n);int ans = 0;for (int i = nums.length - 1; i >= 0; --i) {
ans += bit.query(map.get(nums[i]) - 1);
bit.update(map.get(nums[i]),1);
}return ans;
}
}class BIT {private int[] tree;private int n;public BIT(int n) {this.n = n;this.tree = new int[n + 1];
}public static int lowbit(int x) {return x & (-x);
}public int query(int x) {int ret = 0;while (x != 0) {
ret += tree[x];
x -= lowbit(x);
}return ret;
}public void update(int x,int d) {while (x <= n) {
tree[x]+=d;
x += lowbit(x);
}
}
}