跳轉到

8.3 樹狀陣列BIT#

概念說明#

樹狀陣列（Binary Indexed Tree，又稱 Fenwick Tree） 是「前綴和」專用的精簡結構：支援單點更新與前綴和查詢，兩者皆 O(log n)。若只需要「和」類可逆運算，它比線段樹程式碼短十倍、常數更小。

它的巧妙之處在於用索引的二進位結構組織資料：定義 lowbit(i) = i & (-i)（i 的二進位最低位的 1 所代表的數值），tree[i] 負責管理「以 i 結尾、長度 lowbit(i)」的這段元素。例如 tree[12]（1100）管理長度 4 的段落、tree[11]（1011）管理長度 1。前綴和 sum(i) 就是把 i 依二進位拆成幾段，各段取自 tree——拆解的方式恰好是「每次砍掉最低位的 1」。

操作步驟#

  1. add(i, d)：把位置 i 增加 d。沿途所有「管得到 i」的節點都要更新：i += i & (-i)，直到超出 n。
  2. prefix(i)：求前 i 項和。累加 tree[i] 後 i -= i & (-i)，直到 i 為 0。
  3. range_sum(l, r)：prefix(r) - prefix(l - 1)——這就是為什麼只處理「和」即可。

Python 實作#

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)      # 索引從 1 開始

    def add(self, i, d):               # 位置 i（1-based）增加 d
        while i <= self.n:
            self.tree[i] += d
            i += i & (-i)              # 跳到下一個管得到 i 的節點

    def prefix(self, i):               # 前 i 項的和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)              # 砍掉最低位的 1
        return s

    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)

# 動態計分板：隨時更新分數、隨時查前綴與區間統計
scores = [0, 5, 3, 8, 1, 9]            # 1 號~5 號選手
bit = BIT(len(scores) - 1)
for i in range(1, len(scores)):
    bit.add(i, scores[i])

print(bit.prefix(3))       # 16（5+3+8）
print(bit.range_sum(2, 5)) # 21（3+8+1+9）
bit.add(3, -3)             # 3 號扣 3 分
print(bit.range_sum(2, 5)) # 18

逆序對計數（BIT 的經典應用）：由左往右掃描，每看到元素 x 就查「目前已出現的數中，比 x 大的有幾個」，累加即逆序對數。用值當 BIT 索引，即可在 O(n log n) 內完成——暴力法是 O(n²)。

def count_inversions(a):
    n = max(a)
    bit = BIT(n)
    inv = 0
    for x in reversed(a):       # 由右往左：查比 x 小的已出現數
        inv += bit.prefix(x - 1)
        bit.add(x, 1)
    return inv

print(count_inversions([3, 1, 4, 2]))   # 3：(3,1) (3,2) (4,2)
print(count_inversions([5, 4, 3, 2, 1])) # 10（完全逆序）

BIT、線段樹、前綴和的取捨#

需求 前綴和陣列 BIT 線段樹
建構 O(n) O(n) O(n)
前綴查詢 O(1) O(log n) O(log n)
單點更新 O(n) O(log n) O(log n)
區間 min/max ✗ ✗ ✓
區間更新 ✗ 需兩棵差分 BIT ✓（懶標記）

複雜度分析#

add 與 prefix 都沿二進位位數行走，至多 O(log n) 步；空間恰為 O(n)，程式碼極短、常數極小。建構可逐點 add（O(n log n)）或「父節點 = 子節點相加」的 O(n) 版本。

練習#

  1. 實作 O(n) 建構版 BIT：先複製原陣列，再用 tree[i] += tree[i - lowbit(i)] 式的推導一次建好。
  2. 用 BIT 實作「隊伍插隊」：支援在第 k 個空位插入一人（提示：BIT 存 0/1 佔位，二分搜找第 k 個 1 的位置）。
  3. 對比實驗：n=10⁵ 隨機資料下，比較「樸素陣列（更新 O(1)、查詢 O(n)）」與「BIT」在「5 萬次更新 + 5 萬次區間和查詢」混合負載下的總耗時。