樹狀陣列
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
樹狀陣列 | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 二叉樹 | ||||||||||||||||
發明時間 | 1989年 | ||||||||||||||||
發明者 | 鮑里斯·里亞布科 | ||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/BITDemo.gif/200px-BITDemo.gif)
樹狀陣列或二元索引樹(英語:Binary Indexed Tree),又以其發明者命名為芬威克樹(英語:Fenwick tree),最早由彼得·M·芬威克(Peter M. Fenwick)於1994年以《A New Data Structure for Cumulative Frequency Tables》[1]為題發表在SOFTWARE PRACTICE AND EXPERIENCE。其初衷是解決數據壓縮裏的累積頻率(Cumulative Frequency)的計算問題,現多用於高效計算數列的字首和, 區間和。它可以以的時間得到任意字首和,並同時支援在時間內支援動態單點值的修改。空間複雜度。
結構起源
[編輯]按照彼得·M·芬威克的說法,正如所有的整數都可以表示成2的冪和,我們也可以把一串序列表示成一系列子序列的和。採用這個想法,我們可將一個字首和劃分成多個子序列的和,而劃分的方法與數的2的冪和具有極其相似的方式。一方面,子序列的個數是其二進制表示中1的個數,另一方面,子序列代表的f[i]的個數也是2的冪。[2][3][4]
基本操作
[編輯]預備函數
[編輯]定義一個lowbit
函數,返回參數轉為二進制後,最後一個1的位置所代表的數值。
例如,lowbit(34)
的返回值將是2;而lowbit(12)
返回4;lowbit(8)
返回8。
將34轉為二進制為(0010 0010)2。這裏的「最後一個1」指的是從位往前數,見到的第一個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,用以維護的字首和,則:
具體能用以下方式實現:(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
修改
[編輯]假設現在要將的值增加delta,
那麼,需要將覆蓋的區間包含的值都加上delta,
這個過程可以寫成遞歸,或者普通的迴圈。
需要計算的次數與數據規模N的位元數有關,即這部分的時間複雜度是。
修改函數的C++寫法:
void edit(int i, int delta)
{
for (int j = i; j <= MAX_N; j += lowbit(j))
BIT[j] += delta;
}
求和
[編輯]假設我們需要計算的值。
- 首先,將ans初始化為0,將i初始化為k。
- 將ans的值加上
BIT[i]
。 - 將i的值減去
lowbit(i)
。 - 重複步驟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;
}
時空複雜度
[編輯]- 初始化複雜度最佳為:
- 單次詢問複雜度:,其中N為陣列大小
- 單次修改複雜度:,其中N為陣列大小
- 空間複雜度:
擴充
[編輯]樹狀陣列可以通過維護差分陣列來處理區間修改和單點查詢。具體地,當我們在 增加 時只需執行 edit(l,d)
和 edit(r+1,-d)
。查詢則與單點修改區間查詢相似。
應用
[編輯]逆序對數是一個數列中在它前面有比它大的個數。如4312的逆序對數是0+1+2+2=5。
可以先把數列中的數按大小順序轉化成到的整數(離散化),使得原數列成為一個的排列,建立一個樹狀陣列,用來記錄這樣一個陣列(下標從1算起)的字首和:若排列中的數當前已經出現,則的值為,否則為。初始時陣列的值均為,從排列中的最後一個數開始遍歷,每次在樹狀陣列中查詢有多少個數小於當前的數(即用樹狀陣列查詢陣列目前個數的字首和)並加入計數器,之後對樹狀陣列執行修改陣列第個數值加的操作。
參考文獻
[編輯]- ^ Peter M. Fenwick. A new data structure for cumulative frequency tables. Software: Practice and Experience. 1994, 24 (3): 327–336 [2015-10-24]. doi:10.1002/spe.4380240306. (原始內容存檔於2021-02-25).
- ^ Binary indexed tree-树状数组. [2012-05-09]. (原始內容存檔於2019-08-23).
- ^ Binary Indexed Trees. [2012-05-09]. (原始內容存檔於2016-06-16).
- ^ TopCoder树状数组教程的译文. [2012-11-18]. (原始內容存檔於2013-04-10).
- ^ 存档副本. [2012-05-11]. (原始內容存檔於2019-11-30).
|