最近想說把學過的資料結構筆記記錄下來
最近剛學了一個新的資料結構-BIT(Binary Index Tree)
0.設計動機
它的動機是處理prefix sum
最直觀求解的方法是
可以使用另一個預處理的陣列
將每個位置的prefix sum先行算出
但當需要modify單點值
並且query出想要的prefix sum時
因為預處理的陣列可能要重新算一次
這樣複雜度最差會是O(n)
查詢複查度為O(1)
而BIT就是來解決這個問題的
他能將modify單點後的query的複雜度降為O(lgn)
查詢亦為O(lgn)
(n為陣列元素個數)
1.示意圖
2.實現
為了實現上圖之結構
首先需要一個輔助function用以取得其parent node以及child node
function回傳值為二進位制表示下由右邊數來遇到的第一個1的數為多少
聽起來很饒口
舉個簡單例子
10的二進位制為01010
右邊數來遇到的第一個1的數為00010
也就是2
取得方法也很簡單
利用2進位補數的概念
-10 = 10101 + 1 = 10110
再將01010與10110做and運算
即可取得00010
因此function為
再來就是最重要的兩個function
一個是沿著當前node不斷遍歷其parent node並更新值的update()
要取得當前node之parent node
算法也相當簡單
為當前node之index加上lowbit(index)可得之
function如下
argument的部分
i為當前node之index
change_val為改變量
第二個重要的function為沿著當前index之child node累加求出array前index個數的和
取的child node的算法與上述剛好相反
為當前node之index減去lowbit(index)可得之
因此function如下
argument的部分
i為欲求array前index數之和的index
因此就可支援區間求和, 單點修改等等操作
附上用C++實作之BIT
另外這東西還可以拿來求逆序數對
等我晚點有空再補ㄅ
另外文章可能有所疏漏或觀念錯誤
歡迎大家指正
