樹狀數組, 又名二叉索引樹(Binary Indexed Tree), 利用該結構能夠有效地解決區間和查詢問題, 并且查詢的時間複雜度是O(log N)
字首和查詢
如圖所示, 在原始數組的基礎上我們引入一個輔助數組c[], c[i]代表的含義是數組i的值以及所有遞歸的前驅之和,整個輔助數組看上去像一顆樹, 是以得名. 舉例
-
- sum[3] = a[3] + c[2] = a[3] + a[2] + c[1] = a[3] + a[2] + c[1]
- sum[13] = a[13] + c[12] + c[8], 通過同樣的代入方法遞歸計算c[12], c[8],可以算得c[13] 就是數組13個數值的和
從上面的計算看出, 本來13個值的和, 這裡通過輔助數組隻有3個數相加, 這也就是他能夠O(log N)查詢字首和的秘密, 所有之前的資料按照倍增的思想,隻要達到2的次方的規模即接管和值, c[2], c[4], c[8]均是一個數便計算出和值
現在的問題是如何根據index找出前驅呢
- c[7]的前驅是c[6]
- c[6]的前驅是c[4]
- c[4]的前驅是c[0] (不存在, 即c[4]已經包含前面所有)
- c[12]的前驅是c[8]
咋一看,還真看不出什麼特點, 我們嘗試一下把所有的數值用二進制表示一下
從上面的可以看出, 目前節點到前驅節點是目前節點減去隻有最末尾為1的數, 知道0為止, 至于怎麼求最末尾為1的數,請參考 巧用位運算
- pre = cur - cur & (~cur + 1)
def lowbit(self, i): # return i & (~i + 1) # 因為(~i + 1)是負數的表示方法, 是以可以簡化成下面的寫法 return i & (-i)
字首和的查詢代碼如下
# 字首和查詢, i是數組的index def query(self, i): result = self.c[i] pre = (i+1) - self.lowbit(i+1) while pre > 0: result += self.c[pre-1] pre = pre - self.lowbit(pre) return result
區間和查詢(i, j)
- 其實就是兩個前驅和做下減法 sum(j) - sum(i-1)
- 注意判斷邊界條件 i == 0的情況
樹狀數組的建立(時間複雜度N*O(log N))
- 跟找前驅不一樣, 它本身收集的是前驅的下一個元素到目前元素的和值
- 代碼如下
# 根據數組建立樹狀數組, 自動處理下标, 沒有下标從1開始的要求 def build(self): for i, val in enumerate(self.arr): left = (i+1) - self.lowbit(i+1) self.c[i] = self.arr[i] pre = i while pre > left: self.c[i] += self.c[pre-1] pre = pre - self.lowbit(pre)
原始數組數值更新(隻能單點更新)
- 這個不像raw數組中的數值更新O(1)的時間複雜度
- 除了更新raw數組中的數值, 還要更新輔助數組中對應的值及遞歸所有後繼的值, 時間複雜度O(log N)
- next = cur + cur & (~cur + 1)
- 有利有弊, 加快區間和查詢的情況下, 其實是增加了更新時的負擔, 是以樹狀數組适用于區間查詢頻繁, 而鮮有更新的場景
- 代碼如下
# 單點更新, i是index, value是需要更新的值 def update(self, i, value): # 算出內插補點,友善後繼更新 diff = value - self.arr[i] if diff != 0: self.arr[i] += diff self.c[i] += diff next = (i+1) + self.lowbit(i+1) while next <= len(self.arr)+1: self.c[next-1] += diff next = next + self.lowbit(next)
喜歡本篇内容, 請點選下方贊、在看或分享吧!?