樹狀陣列

樹狀陣列
類型	二叉樹
發明時間	1989年
發明者	鮑里斯·里亞布科
用大O符號表示的時間複雜度
演算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$

根據陣列[1, 2, 3, 4, 5]來建立對應的樹狀陣列

樹狀陣列或二元索引樹（英語：Binary Indexed Tree），又以其發明者命名為芬威克樹（英語：Fenwick tree），最早由彼得·M·芬威克（Peter M. Fenwick）於1994年以《A New Data Structure for Cumulative Frequency Tables》為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裏的累積頻率（Cumulative Frequency）的計算問題，現多用於高效計算數列的字首和， 區間和。它可以以$O(\log n)$的時間得到任意字首和$\sum _{i=1}^{j}A[i],1<=j<=N$，並同時支援在$O(\log n)$時間內支援動態單點值的修改。空間複雜度$O(n)$。

結構起源

按照彼得·M·芬威克的說法，正如所有的整數都可以表示成2的冪和，我們也可以把一串序列表示成一系列子序列的和。採用這個想法，我們可將一個字首和劃分成多個子序列的和，而劃分的方法與數的2的冪和具有極其相似的方式。一方面，子序列的個數是其二進制表示中1的個數，另一方面，子序列代表的f[i]的個數也是2的冪。

基本操作

預備函數

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

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

將34轉為二進制為(0010 0010)₂。這裏的「最後一個1」指的是從$2^{0}$位往前數，見到的第一個1，也就是$2^{1}$位上的1。

程式上，(~i + 1) & i表明了最後一位1的值。

仍然以34為例，~(0010 0010)的結果是1101 1101（221），加1後為1101 1110（222），把0010 0010與1101 1110作AND，得0000 0010（2）。

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

int lowbit(int x)
{
    return x&(-x);
}

新建

定義一個陣列 BIT，用以維護$A$的字首和，則：$BIT_{i}=\sum _{j=i-lowbit(i)+1}^{i}A_{j}$

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

void build()
{ 
    for (int i = 1; i <= MAX_N; i++)
    {
        BIT[i] = A[i - 1];
        for (int j = i - 2; j >= i - lowbit(i); j--)
            BIT[i] += A[j];
    }
}
//注：这里的求和将汇集到非终端结点（D00形式）
//BIT中仅非终端结点i值是 第0~i元素的和
//终端结点位置的元素和，将在求和函数中求得
//BIT中的index，比原数组中大1

修改

假設現在要將$A[i]$的值增加delta，

那麼，需要將$BIT[i]$覆蓋的區間包含$A[i]$的值都加上delta，

這個過程可以寫成遞歸，或者普通的迴圈。

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

修改函數的C++寫法：

void edit(int i, int delta)
{
    for (int j = i; j <= MAX_N; j += lowbit(j))
        BIT[j] += delta;
}

求和

假設我們需要計算$\sum _{i=1}^{k}A_{i}$的值。

1. 首先，將ans初始化為0，將i初始化為k。
2. 將ans的值加上BIT[i]。
3. 將i的值減去lowbit(i)。
4. 重複步驟2～3，直到i的值變為0。

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

int sum (int k)
{
    int ans = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ans += BIT[i];
    return ans;
}

時空複雜度

• 初始化複雜度最佳為：$O(N)$
• 單次詢問複雜度：$O(\log N)$，其中N為陣列大小
• 單次修改複雜度：$O(\log N)$，其中N為陣列大小
• 空間複雜度：$O(N)$

擴充

樹狀陣列可以通過維護差分陣列來處理區間修改和單點查詢。具體地，當我們在 $[l,r]$ 增加 $d$ 時只需執行 edit(l,d) 和 edit(r+1,-d) 。查詢則與單點修改區間查詢相似。

應用

求逆序對數

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

可以先把數列中的數按大小順序轉化成$1$到$n$的整數（離散化），使得原數列成為一個$1,2,...,n$的排列$P$，建立一個樹狀陣列，用來記錄這樣一個陣列$A$（下標從1算起）的字首和：若排列中的數$i$當前已經出現，則$A[i]$的值為$1$，否則為$0$。初始時陣列$A$的值均為$0$，從排列中的最後一個數開始遍歷，每次在樹狀陣列中查詢有多少個數小於當前的數$P[j]$（即用樹狀陣列查詢陣列$A$目前$P[j]-1$個數的字首和）並加入計數器，之後對樹狀陣列執行修改陣列$A$第$P[j]$個數值加$1$的操作。