跳至主要内容

Segment Tree

Segment Tree 是一種專門用來處理「區間查詢」（例如區間和、區間最大/最小值）的二元樹結構，而且把陣列裡的值改掉之後，查詢依然維持 O(log n)。

想像一個情形：如果只用一個陣列 + Prefix Sum，區間查詢雖然可以做到 O(1)，但只要陣列裡有任何一個值被修改，整個 Prefix Sum 陣列可能要花 O(n) 重建；如果完全不做任何預處理，區間查詢退化成每次都 O(n) 掃過去。

Segment Tree 就是在「查詢快」跟「更新快」兩者之間找到的平衡點，讓查詢、更新都是 O(log n)。

白話理解

想像一個企業的組織圖：最上面是執行長，往下是各部門主管，再往下是小組長，最底層才是每一個員工。如果老闆想知道「整個業務部這個月的業績總和」，不需要去問業務部底下每一個員工，只要問業務部主管一個人就好，因為主管早就已經彙總好底下所有小組的數字了。

Segment Tree 就是這種「每一層都先幫你把底下的答案彙總好」的結構：陣列的每一段區間，都有一個節點事先算好「這一段的答案是什麼」，查詢任何範圍時，只需要湊幾個「剛好涵蓋這個範圍」的節點加起來，不需要真的把整個範圍重新算一次。

核心結構：用 Node 物件建立一棵二元樹​

Segment Tree 常見的實作方式有兩種：一種是跟 Heap 一樣，用一個 Array 搭配 2*i+1、2*i+2 的索引運算模擬二元樹；另一種則是像一般的 Binary Tree 一樣，每個節點都是一個獨立的 Node 物件，自己記住「負責的區間範圍 [start, end]」、「這個區間的彙總答案」，並用 left、right 兩個指標直接連到左右子節點。這篇文章採用後者「Node 物件」的寫法，結構跟一般的 Tree 更接近，也不需要像陣列版本那樣煩惱「陣列要開多大才安全」。

每個節點負責把自己管轄的區間 [start, end]，從中間切成兩半分給左右子節點，再把子節點的答案合併起來存在自己身上：

原始陣列（index）：  0    1    2    3    4    5
原始陣列（值）：     1    3    5    7    9   11

對應的 Segment Tree（每個節點標示自己管轄的區間，與區間和）：

                      [0,5]=36
                     /         \
               [0,2]=9           [3,5]=27
              /       \          /       \
         [0,1]=4    [2,2]=5  [3,4]=16   [5,5]=11
         /    \                /    \
    [0,0]=1  [1,1]=3     [3,3]=7  [4,4]=9

每個葉節點（start === end）對應陣列裡的一個元素，往上每一層都是「左右兩個子節點的答案合併」。

由於每次都是從中間對半切，樹高是 O(log n)，而且整棵樹剛好只會有 2n - 1 個節點（n 個葉節點 + n - 1 個內部節點），不需要像陣列版本一樣額外抓 4n 當安全上限，這是 Node 物件版本相對直覺的地方，代價是每個節點要額外存兩個指標（left、right），記憶體的常數因子會比純陣列版本略大。

實作：建樹、區間查詢、單點更新​

下面以「區間和」為例（node.sum 存的是這個節點管轄區間的總和），示範最基本的 Segment Tree，先不處理區間更新：

class SegmentTreeNode:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end
        self.sum = 0          # 這個節點管轄區間的總和
        self.left = None      # 左子節點
        self.right = None     # 右子節點


class SegmentTree:
    def __init__(self, nums: list[int]):
        self.root = self._build(nums, 0, len(nums) - 1)

    def _build(self, nums, start, end) -> SegmentTreeNode:
        node = SegmentTreeNode(start, end)
        if start == end:
            node.sum = nums[start]  # 葉節點：直接存陣列原本的值
            return node
        mid = start + (end - start) // 2
        node.left = self._build(nums, start, mid)
        node.right = self._build(nums, mid + 1, end)
        node.sum = node.left.sum + node.right.sum  # 往上合併（push up）
        return node

    def update(self, index: int, val: int, node: SegmentTreeNode = None):
        """單點更新：把 nums[index] 改成 val"""
        if node is None:
            node = self.root

        if node.start == node.end:
            node.sum = val  # 找到葉節點，直接覆蓋
            return

        mid = node.start + (node.end - node.start) // 2
        if index <= mid:
            self.update(index, val, node.left)
        else:
            self.update(index, val, node.right)
        node.sum = node.left.sum + node.right.sum  # 往上重新合併

    def query(self, l: int, r: int, node: SegmentTreeNode = None) -> int:
        """查詢區間 [l, r] 的和"""
        if node is None:
            node = self.root

        if r < node.start or node.end < l:
            return 0  # 完全沒交集，對答案沒有貢獻

        if l <= node.start and node.end <= r:
            return node.sum  # 這個節點管轄的區間完全被 [l, r] 包住，直接回傳現成答案

        return self.query(l, r, node.left) + self.query(l, r, node.right)

query 的三個分支是整個 Segment Tree 最核心的邏輯，務必理解每一種情況：

  1. 完全沒交集（r < node.start 或 node.end < l）：這個節點管轄的區間跟要查詢的 [l, r] 完全沒有重疊，直接回傳 0（對和沒有貢獻），不用往下遞迴。
  2. 完全被包住（l <= node.start 且 node.end <= r）：這個節點管轄的區間完全落在 [l, r] 裡面，代表 node.sum 現成算好的答案就是正確答案，直接回傳，不用再往下拆。
  3. 部分重疊：剩下的情況，只好往 node.left、node.right 各自查詢，再把結果合併。

這三個分支保證了每一層遞迴最多只會有常數個節點需要「部分重疊」往下拆，因此整體時間複雜度是 O(log n)，而不是每次都要走訪所有節點。

當更新變成「一整段區間」：為什麼需要 Lazy Propagation​

上面的 update 只能改單一個 index，如果題目要求「把 [l, r] 這段範圍的每個元素都加上某個值」，照直覺的寫法會是：對 [l, r] 裡的每一個 index 都呼叫一次 update，每次 O(log n)，一段長度 k 的區間就要花 O(k log n)。當 k 接近 n，整個 Segment Tree 省下來的優勢就被這個「逐一更新」的迴圈吃光了。

Lazy Propagation（延遲標記） 解決的正是這個問題：當某個節點管轄的區間「完全被要更新的範圍包住」時，先不要往下更新子節點，只在這個節點上記一筆「帳」，也就是「我底下欠了多少還沒加上去的值」，等到之後真的需要往下查詢或更新子節點時，才把這筆帳「下推（push down）」給子節點。這樣一來，區間更新跟區間查詢一樣都只需要 O(log n)。

白話理解

延續組織圖的比喻：老闆說「業務部全體加薪 10%」，業務部主管不需要立刻一個一個去改每個員工的薪資單，只要在自己的筆記本記一筆「底下所有人都要加薪 10%，還沒發公告」就好，彙總的總薪資數字可以馬上更新。等到哪天小組長真的要去查「某個員工目前的薪資」時，主管才需要把這筆帳正式下推給小組長，小組長再視情況繼續往下推給員工。

實作：push down、區間更新、區間查詢​

延續上面的區間和範例，SegmentTreeNode 額外多一個 lazy 欄位，代表「這個節點底下還欠多少還沒下推給子節點的加法」：

class SegmentTreeNode:
    def __init__(self, start: int, end: int):
        self.start = start
        self.end = end
        self.sum = 0       # 這個節點管轄區間的總和
        self.lazy = 0      # 延遲標記：這個節點底下還欠多少還沒下推的加法
        self.left = None
        self.right = None


class SegmentTreeLazy:
    def __init__(self, nums: list[int]):
        self.root = self._build(nums, 0, len(nums) - 1)

    def _build(self, nums, start, end) -> SegmentTreeNode:
        node = SegmentTreeNode(start, end)
        if start == end:
            node.sum = nums[start]
            return node
        mid = start + (end - start) // 2
        node.left = self._build(nums, start, mid)
        node.right = self._build(nums, mid + 1, end)
        node.sum = node.left.sum + node.right.sum
        return node

    def _push_down(self, node: SegmentTreeNode):
        if node.lazy == 0:
            return  # 沒有欠任何更新，不用做事

        # 把欠的值，分別記到左右子節點的帳本上，子節點的區間和也要同步更新
        for child in (node.left, node.right):
            child.lazy += node.lazy
            child.sum += node.lazy * (child.end - child.start + 1)

        node.lazy = 0  # 帳已經下推給子節點，自己歸零

    def update_range(self, l: int, r: int, val: int, node: SegmentTreeNode = None):
        """把 [l, r] 範圍內的每個元素都加上 val"""
        if node is None:
            node = self.root

        if r < node.start or node.end < l:
            return  # 完全沒交集，不用管

        if l <= node.start and node.end <= r:
            # 完全被 [l, r] 包住：直接更新這個節點的總和，欠的值記在這裡就好，不往下推
            node.sum += val * (node.end - node.start + 1)
            node.lazy += val
            return

        self._push_down(node)  # 要往下走之前，先把欠子節點的帳還清
        self.update_range(l, r, val, node.left)
        self.update_range(l, r, val, node.right)
        node.sum = node.left.sum + node.right.sum  # 往上合併

    def query_range(self, l: int, r: int, node: SegmentTreeNode = None) -> int:
        """查詢區間 [l, r] 的和"""
        if node is None:
            node = self.root

        if r < node.start or node.end < l:
            return 0

        if l <= node.start and node.end <= r:
            return node.sum

        self._push_down(node)  # 要往下走之前，先把欠子節點的帳還清
        return self.query_range(l, r, node.left) + self.query_range(l, r, node.right)
push_down 不是只有區間更新才需要

query_range 裡也呼叫了 _push_down，這是很容易漏掉的地方：如果某個節點之前被標記了「欠款」但還沒下推，子節點的 sum 其實是過期的，這時候如果查詢剛好需要往下拆到子節點，卻沒有先 push_down，就會讀到錯誤的舊值。任何時候只要準備要往下遞迴到子節點，不管是更新還是查詢，都要先 push_down。

push_down 只會作用在非葉節點

葉節點（start === end）沒有 left、right，一旦遞迴走到葉節點，一定會先滿足「完全被 [l, r] 包住」而直接回傳，不會進入需要 push_down 的分支。但如果程式邏輯寫錯、不小心對葉節點呼叫了 push_down，存取 node.left.lazy 就會因為 node.left 是 None/null 而噴錯。

逐步拆解：以 nums = [1, 3, 5, 7, 9, 11] 為例​

先 build 出跟前面「核心結構」小節一樣的樹，接著執行 update_range(1, 3, 10)（把 index 1～3 都加上 10），下表用每個節點管轄的區間來代表該節點：

節點（區間）判斷動作
root [0,5]跟 [1,3] 部分重疊往下遞迴，先 push_down（目前沒欠帳，略過）
[0,2]跟 [1,3] 部分重疊往下遞迴
[0,1]跟 [1,3] 部分重疊往下遞迴
[0,0]跟 [1,3] 完全沒交集直接返回，不處理
[1,1]完全被 [1,3] 包住sum += 10*1 = 10 → 變成 13；lazy += 10
[2,2]完全被 [1,3] 包住sum += 10*1 = 10 → 變成 15；lazy += 10
[3,4]跟 [1,3] 部分重疊往下遞迴
[3,3]完全被 [1,3] 包住sum += 10*1 = 10 → 變成 17；lazy += 10
[4,4]跟 [1,3] 完全沒交集直接返回，不處理
[5,5]跟 [1,3] 完全沒交集直接返回，不處理

一路往上合併之後，整棵樹對應的陣列變成 [1, 13, 15, 17, 9, 11]（只有 index 1、2、3 被加上了 10），過程中完全沒有走訪 [4,4]、[5,5]、[0,0] 這些跟更新範圍無關的節點內部，真正被「展開到葉節點」處理的只有邊界附近的節點，中間被完整包住的節點（例如如果更新範圍是 [0,5] 這種整段）甚至不需要往下走一步，直接在 root 記一筆帳就結束，這正是 Lazy Propagation 省下時間的地方。

複雜度​

操作沒有 Lazy Propagation有 Lazy Propagation
Build（建樹）O(n)O(n)
單點查詢 / 更新O(log n)O(log n)
區間查詢O(log n)O(log n)
區間更新O(k log n)（k 是更新範圍大小，逐一呼叫單點更新）O(log n)
空間複雜度O(n)（恰好 2n - 1 個 Node 物件）O(n)（每個 Node 多一個 lazy 欄位）
資訊

Lazy Propagation 只有在區間更新的情境下才有意義。如果題目只需要單點更新 + 區間查詢（例如 LeetCode 307. Range Sum Query - Mutable），不需要 lazy 欄位，直接用前面「核心結構」小節的基本版本就夠了，不用為了「以防萬一」而多寫一層複雜度。

適用情況​

  • 區間查詢 + 單點更新：例如 LeetCode 307. Range Sum Query - Mutable，陣列會動態修改某個元素，同時要頻繁查詢任意區間的和。
  • 區間查詢 + 區間更新：例如「同時處理大量『把某段範圍全部加上某個值』與『查詢某段範圍的總和/最大值』」的題目，這正是 Lazy Propagation 派上用場的場景，例如 LeetCode 2940. Find Building Where Alice and Bob Can Meet、LeetCode 732. My Calendar III 這類需要動態維護區間資訊的題目。
  • 取代巢狀迴圈暴力解：只要題目的操作型態是「反覆進行區間查詢與區間/單點更新交錯出現」，且資料量大到 O(n) 或 O(n²) 會超時，Segment Tree 幾乎都能把每個操作壓到 O(log n)。
  • RMQ（Range Minimum/Maximum Query）：把 node.sum 存的「區間和」換成「區間最小值/最大值」，push up 時用 min/max 取代 +，就能解決區間極值查詢問題，是 Segment Tree 另一個經典應用。
跟 Fenwick Tree（Binary Indexed Tree）的取捨

如果題目只需要「區間和 + 單點更新」，不需要區間更新、也不需要處理最大/最小值這類不能直接做差分的運算，Fenwick Tree（又稱 Binary Indexed Tree）的程式碼通常比 Segment Tree 更短、常數更小。但 Fenwick Tree 的技巧比較依賴「運算具有可差分性」（像加法可以用減法還原），遇到區間最大/最小值、區間更新這類需求時，Segment Tree（搭配 Lazy Propagation）的彈性比 Fenwick Tree 大得多，這也是為什麼面試或競賽中 Segment Tree 的應用範圍通常被認為更廣。

常見誤區​

  • 忘記在遞迴往下之前 push_down：不管是 update_range 還是 query_range，只要函式裡有「往下遞迴到子節點」的分支，前面就一定要先呼叫 push_down，漏掉的話子節點的值可能是過期的，查詢或更新都會算錯。
  • push_down 之後忘記把自己的 lazy 歸零：欠款下推給子節點之後，自己的帳本（node.lazy）一定要清空，不然下次又會被重複加算一次，同一筆更新被套用了兩次。
  • 對葉節點呼叫 push_down：葉節點的 left、right 是 None/null，正常邏輯不會走到這裡（見上面的提醒），但如果 query/update 的三個分支判斷寫錯順序，誤將「完全被包住」的檢查放到 push_down 之後，有可能在葉節點上也觸發 push_down，直接噴出 Null Pointer 相關的錯誤。
  • 區間邊界搞錯 inclusive/exclusive：這份實作全程使用「雙閉區間」[l, r]（頭尾都包含），混用成一半開區間容易在邊界元素上算錯或漏算，動手寫之前先確認自己使用的是哪一種慣例，並且全程保持一致。
  • 誤以為 Lazy Propagation 對所有運算都適用同一套公式：這裡示範的是「區間加法 + 區間和」，push_down 時用 node.lazy * 區間長度 來更新 sum；但如果運算換成「區間賦值（把整段都改成同一個值）」或「區間乘法」，push_down 的合併公式會完全不同，直接套用區間加法的公式會得到錯誤答案，動手寫之前要先想清楚自己的 lazy 標記代表的是哪一種操作。
  • 在不需要區間更新的題目上硬套 Lazy Propagation：如同上面「複雜度」小節提醒的，只有單點更新需求時，多維護一個 lazy 欄位只是徒增程式碼複雜度，沒有實質效能幫助。

參考資料：

最後於 更新