線段樹：區間的計算器

演算法背後的故事：動態倉庫

想像一個有 100 個貨架的倉庫。每個貨架上都有一定數量的箱子。 經理會問兩類問題：

1. 更新： 「5 號貨架剛多了 3 個箱子。」
2. 查詢： 「從 10 號貨架到 50 號貨架總共有多少個箱子？」

• 如果妳使用普通陣列，更新 很快 ($O(1)$)，但 查詢 很慢 ($O(N)$ - 妳必須走過 40 個貨架)。
• 如果妳使用預計算的前綴和陣列，查詢 很快 ($O(1)$)，但 更新 很慢 ($O(N)$ - 妳必須重新計算 5 號之後的所有和)。

線段樹 (Segment Tree) 是中庸之道。它讓這兩種操作都變得很快 ($O(\log N)$)。它將貨架分組（1-50, 51-100），並分層（1-25, 26-50），然後記住每個組的總和。

為什麼需要它？

• 計算幾何： 尋找重疊的矩形。
• 分析： 「上午 10:00 到下午 2:00 之間的最高股價是多少？」（區間最大值查詢）。
• 遊戲開發： 「在 X 座標的這個範圍內有牆嗎？」

演算法是如何「思考」的

這個演算法是一個分層聚合器。

1. 葉子： 原始陣列的元素是樹的葉子。
2. 內部節點： 每個父節點儲存其兩個孩子的 總和（或最小值/最大值）。
3. 查詢： 要找到區間 $[L, R]$ 的總和，我們不查看單獨的葉子。我們尋找能放入 $[L, R]$ 內的最巨大的預計算「塊」，並將她們加起來。
4. 更新： 當葉子發生變化時，我們向上走到根，只更新受影響的父節點。

工程決策：懶惰傳播 (Lazy Propagation)

進階版本使用 懶惰傳播。

• 如果妳想「給 1 到 50 號貨架的每個貨架都加 5 個箱子」，一個個加太慢了。
• 相反，妳在代表 [1-50] 的節點上貼一張「便利貼」（懶標記），上面寫著「+5」。直到有人真正查到她的孩子時，妳才去更新她們。這使得區間更新也變成了 $O(\log N)$。

實作參考 (Python)

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        # 樹的大小大約是 4*n
        self.tree = [0] * (4 * self.n)
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        if start == end:
            self.tree[node] = data[start]
        else:
            mid = (start + end) // 2
            self._build(data, 2 * node, start, mid)
            self._build(data, 2 * node + 1, mid + 1, end)
            # 範例：求和查詢
            self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

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

    def _update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val
        else:
            mid = (start + end) // 2
            if start <= idx <= mid:
                self._update(2 * node, start, mid, idx, val)
            else:
                self._update(2 * node + 1, mid + 1, end, idx, 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, start, end, l, r):
        if r < start or end < l:
            return 0 # 超出範圍
        if l <= start and end <= r:
            return self.tree[node] # 完全在範圍內
        
        mid = (start + end) // 2
        p1 = self._query(2 * node, start, mid, l, r)
        p2 = self._query(2 * node + 1, mid + 1, end, l, r)
        return p1 + p2

# 使用範例
data = [1, 3, 5, 7, 9, 11]
st = SegmentTree(data)
print(f"索引 1 到 3 的和: {st.query(1, 3)}") # 3+5+7 = 15
st.update(1, 10) # 把 3 改成 10
print(f"新和: {st.query(1, 3)}") # 10+5+7 = 22

小結

線段樹教會我們：聚合能節省時間。透過預先計算群體的摘要，我們無需檢查每一個「部分」就能回答關於「整體」的問題。她提醒我們，在數據分析中，縮小視野看到大局的能力與原始數據本身一樣重要。