<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Fenwick Tree(Binary Indexed Tree) - 樹狀數組（二進制索引樹） -------- #### 樹狀數組（二進制索引樹） 對于區間$$ s = [x_{1}, x_{2}, x_{3}, \dots, x_{n}] $$，求區間$$ s[p,q) $$（其中$$ 1 \leq p \lt q \leq n $$）上的所有成員之和（簡稱區域和/區間和）。區間上任意位置$$ s[i] $$的值可以修改，但所有元素都恒為非負整數。 循環累加數組的算法和SegmentTree算法都可以解決該問題，Fenwick樹（樹狀數組/二進制索引樹）與SegmentRee同樣在時間復雜度$$ O(log_2 n) $$內求出某個區域上的和，但空間復雜度更低。實際上由于字節操作，FenwickTree不但占用內存少，且速度更快（內存更緊湊的軟件速度更快）。 設$$ sum(n) = \sum_{i=1}^{n} s[i] $$，那么$$ s[p,q) $$的區間和可以表示為$$ sum(q-1) - sum(p-1) $$。本問題可以轉化為求區間$$ s $$上前$$ n $$個元素之和的問題。 FenwickTree的靈感來源于任意非負整數都可以表示為$$ 2 $$的次方和，比如$$ 3 = 2^1 + 2^0, 7 = 2^2 + 2^1 + 2^0, 8 = 2^3 $$。所以任意非負整數可以用一個代表bit的數組表示：$$ 3 = [0, 0, 1, 1] $$，$$ 7 = [0, 1, 1, 1] $$，$$ 8 = [1, 0, 0, 0] $$，即二進制數字$$ 0011, 0111, 1000 $$。那么區域$$ s $$可以用$$ n $$個二進制數組來表示所有數字，用Fenwick樹結構來表示：  引入最低有效位lowbit函數來構造Fenwick樹上的每個節點。$$ lowbit $$是一個非負整數的二進制數字中，最低的非$$ 0 $$位的數字（比如$$ lowbit_{3} = 1, lowbit_{6} = 2, lowbit_{8} = 8, lowbit_{11} = 1 $$，顯然奇數有$$ lowbit_{ord} \equiv 1 $$）：  令Fenwick樹上的節點$$ x $$存儲值$$ t[x] $$： $$ t[x] = \sum_{i=x-lowbit(x)+1}^{x} s[i] $$ 比如： $$ \begin{matrix} t[1] & = \sum_{i=1-1+1}^{1} s[i] & = \sum_{i=1}^{1} s[i] & = s[1] & x=1 \\ t[2] & = \sum_{i=2-2+1}^{2} s[i] & = \sum_{i=1}^{2} s[i] & = s[1] + s[2] & x=2 \\ t[3] & = \sum_{i=3-1+1}^{3} s[i] & = \sum_{i=3}^{3} s[i] & = s[3] & x=3 \\ t[4] & = \sum_{i=4-4+1}^{4} s[i] & = \sum_{i=1}^{4} s[i] & = s[1] + \cdots + s[4] & x=4 \\ t[5] & = \sum_{i=5-1+1}^{5} s[i] & = \sum_{i=5}^{5} s[i] & = s[5] & x=5 \\ t[6] & = \sum_{i=6-2+1}^{6} s[i] & = \sum_{i=5}^{6} s[i] & = s[5] + s[6] & x=6 \\ t[7] & = \sum_{i=7-1+1}^{7} s[i] & = \sum_{i=7}^{7} s[i] & = s[7] & x=7 \\ t[8] & = \sum_{i=8-8+1}^{8} s[i] & = \sum_{i=1}^{8} s[i] & = s[1] + \cdots + s[8] & x=8 \\ t[9] & = \sum_{i=9-1+1}^{9} s[i] & = \sum_{i=1}^{9} s[i] & = s[9] & x=9 \\ t[10] & = \sum_{i=10-2+1}^{10} s[i] & = \sum_{i=9}^{10} s[i] & = s[9] + s[10] & x=10 \\ t[11] & = \sum_{i=11-1+1}^{11} s[i] & = \sum_{i=11}^{11} s[i] & = s[11] & x=11 \\ t[12] & = \sum_{i=12-4+1}^{12} s[i] & = \sum_{i=9}^{12} s[i] & = s[9] + \cdots + s[12] & x=12 \\ t[13] & = \sum_{i=13-1+1}^{13} s[i] & = \sum_{i=13}^{13} s[i] & = s[13] & x=13 \\ t[14] & = \sum_{i=14-2+1}^{14} s[i] & = \sum_{i=13}^{14} s[i] & = s[13] + s[14] & x=14 \\ t[15] & = \sum_{i=15-1+1}^{15} s[i] & = \sum_{i=15}^{15} s[i] & = s[15] & x=15 \\ t[16] & = \sum_{i=16-16+1}^{16} s[i] & = \sum_{i=1}^{16} s[i] & = s[1] + \cdots + s[16] & x=16 \\ \cdots \end{matrix} $$ Fenwick樹上每個節點$$ i $$覆蓋到的區域之和如圖所示：  設數字$$ x $$用$$ 2 $$的次方和表示為： $$ x = [bit_{1}, bit_{2}, \dots, bit_{m}] $$ 比如$$ 6 = [4, 2], 8 = [8], 10 = [8, 2] $$。那么恰好有： $$ sum(x) = t[x] + sum(x - lowbit(x)) $$ 求非負整數$$ x $$的最低有效位分為以下幾步： $$ (1) $$ 減1使$$ x $$的最低有效位變為0（$$ x - 1 $$），最低有效位之前的那些0變為1，比如$$ 1000 - 1 = 111 $$； $$ (2) $$ 然后異或操作（$$ x \oplus (x-1) $$）就可以將$$ x $$的最低有效位及之前的所有位設置為1，比如$$ 1000 \oplus 0111 = 1111 $$； $$ (3) $$ 最后與原$$ x $$做與操作（$$ x \wedge (x \oplus (x-1)) $$），結果即為最低有效位對應的數字； lowbit函數的C++實現如下： ``` c++ int LowBit(int x) { return x & (x ^ (x-1)); } ``` 或者利用反碼特性，實現為： ``` c++ int LowBit(int x) { return x & (-x); } ``` 對于長度為$$ n $$的區域$$ s $$，構造Fenwick樹的時間復雜度為$$ O(n \cdot log_2?n) $$，查詢區域和的時間復雜度為$$ O(log_2 n) $$，修改區域上一個值的時間復雜度為$$ O(log_2?n) $$，空間復雜度為$$ O(n) $$。 -------- #### 二進制索引樹 * http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=07BA8E50FC6C41AAE5CFCE28AEB9656E?doi=10.1.1.14.8917&rep=rep1&type=pdf * https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/ -------- #### 源碼 [FenwickTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/FenwickTree.h) [FenwickTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/FenwickTree.cpp) #### 測試 [FenwickTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/FenwickTreeTest.cpp)