跳轉到

8.2 區間樹與線段樹#

概念說明#

典型問題：陣列支援兩種操作——更新某元素與查詢某區間的和（或最大、最小）。

  • 樸素陣列：更新 O(1)、區間查詢 O(n)。
  • 前綴和陣列：查詢 O(1)、但更新後要重算 O(n)。

線段樹（segment tree） 讓兩者都達到 O(log n)。它把陣列切成區間：根代表整個陣列，每個節點把區間對半分給兩個小孩，葉代表單一元素；節點上存該區間的統計值（和、最大值……）。查詢時把 [l, r] 拆解成樹上 O(log n) 個節點合併；更新時只修正「包含該元素」的那條路徑。

區間樹（interval tree） 則是另一個概念：儲存一組「區間」，支援「找出所有與查詢區間重疊的區間」（如行事曆衝突檢測）。它以區間左端點為 BST 鍵、每節點額外記錄子樹最大右端點，查詢 O(log n + k)。本節以線段樹為主體，區間樹在練習中延伸。

操作步驟#

  1. build(node, lo, hi)：葉時直接存元素；否則遞迴建左右子樹，節點值 = 左右子節點值合併。
  2. query(node, lo, hi, l, r)：若節點區間與查詢區間不相交，回「單位元」；若節點區間完全落在查詢區間內，直接回節點值；否則分別查左右子樹再合併。
  3. update(node, lo, hi, i, val)：沿包含 i 的路徑下行，到葉改值，回程重新合併。

Python 實作#

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)      # 4n 大小必然夠用
        if self.n:
            self._build(1, 0, self.n - 1, data)

    def _build(self, node, lo, hi, data):
        if lo == hi:
            self.tree[node] = data[lo]
            return
        mid = (lo + hi) // 2
        self._build(2*node, lo, mid, data)
        self._build(2*node + 1, mid + 1, hi, data)
        self.tree[node] = self.tree[2*node] + self.tree[2*node + 1]

    def update(self, i, val):
        self._update(1, 0, self.n - 1, i, val)

    def _update(self, node, lo, hi, i, val):
        if lo == hi:
            self.tree[node] = val
            return
        mid = (lo + hi) // 2
        if i <= mid:
            self._update(2*node, lo, mid, i, val)
        else:
            self._update(2*node + 1, mid + 1, hi, i, val)
        self.tree[node] = self.tree[2*node] + self.tree[2*node + 1]

    def query(self, l, r):
        return self._query(1, 0, self.n - 1, l, r)

    def _query(self, node, lo, hi, l, r):
        if r < lo or hi < l:                # 不相交
            return 0                        # 「和」的單位元
        if l <= lo and hi <= r:             # 完全包含
            return self.tree[node]
        mid = (lo + hi) // 2
        return (self._query(2*node, lo, mid, l, r) +
                self._query(2*node + 1, mid + 1, hi, l, r))

st = SegmentTree([2, 5, 1, 4, 9, 3])
print(st.query(1, 4))       # 5+1+4+9 = 19
st.update(2, 100)           # 陣列 [2, 5, 100, 4, 9, 3]
print(st.query(1, 4))       # 118
print(st.query(0, 5))       # 123

若要支援「區間整體加值」的懶惰標記（lazy propagation）：更新整段時不真的下修每個葉，而是在節點掛一個「這段每人都加了 d」的標記，等後續查詢/更新走到該節點才下放標記，可把區間更新也降到 O(log n)。

複雜度分析#

建樹 O(n)（n 個葉、共約 2n 個節點各合併一次）；單點更新與區間查詢皆 O(log n)；空間 O(n)。懶惰標記版可把區間更新也做到 O(log n)。

練習#

  1. 把線段樹的合併運算改成「區間最大值」，實作 range_max(l, r)，注意不相交時要回 −∞ 而非 0。
  2. 實作懶惰標記版本：支援 range_add(l, r, d)（區間每個元素加 d）與 range_sum(l, r)，兩者皆 O(log n)。
  3. （區間樹）節點存 (start, end) 區間，額外維護子樹最大 end；實作 overlap_query(qs, qe)：回傳所有與 [qs, qe] 重疊的區間，並用行事曆資料（含一組衝突會議）測試。