Segment Tree

Binary Tree 和 Segment Tree 有什麼不同？

Binary Tree（二元樹）描述的是樹的形狀：每個節點最多有兩個子節點。這個定義沒有指定節點要存什麼資料，也沒有規定要支援哪一種查詢。

Segment Tree（線段樹）是為了維護區間資料而設計的資料結構：它用二元樹把陣列的索引範圍分段，每個節點保存一段範圍的摘要，例如總和、最大值、最小值或 GCD。

所以，線段樹通常會長成二元樹，但二元樹不一定是線段樹。Binary Tree 講「結構」；Segment Tree 講「如何用樹維護區間答案」。

比較面向	Binary Tree（二元樹）	Segment Tree（線段樹）
定義	每個節點最多有兩個子節點	把索引範圍分段，節點保存區間摘要
節點存什麼	沒有限定	總和、最值、GCD 等可合併的資訊
用途	本身不指定操作；BST、Heap 等會再加上規則	反覆查詢區間，也可在資料更新後快速維護
複雜度	沒有單一答案，要看額外規則和樹高	基本型建樹 \(O(n)\)，查詢與單點更新 \(O(\log n)\)（假設合併為 \(O(1)\)）

左側只展示二元樹的形狀規則；右側以 \(A=[20,40,60,80]\) 為例，節點同時記錄索引區間和該區間的 GCD。橘色節點代表查詢 \([0,2]\) 時可直接重用的兩段摘要：\([0,1]\) 和 \([2,2]\)。

若要先複習二元樹的基本定義，可以看 Vault 筆記二元樹 (Binary Tree)，或閱讀二元樹 Blog 文章。

用 GCD 走一次查詢和更新

以下陣列使用 0-based、左右端點皆包含的索引：

\[ A=[20,40,60,80] \]

每個葉節點存一個陣列值；父節點把左右子節點的答案合併：

G_v=\gcd(G_{\mathrm{left}(v)},G_{\mathrm{right}(v)})

查詢區間 \([0,2]\) 時，線段樹把它拆成已經算好的 \([0,1]\)，以及葉節點 \([2,2]\)：

\begin{aligned} G_{[0,1]} &= \gcd(20,40)=20,\\ G_{[2,2]} &= 60,\\ G_{[0,2]} &= \gcd(G_{[0,1]},G_{[2,2]})=\gcd(20,60)=20. \end{aligned}

查詢 \([1,2]\) 則跨過左右子樹的分界，會取出 \(40\) 和 \(60\)，再計算 \(\gcd(40,60)=20\)。兩種查詢都只處理少數相關節點，不必逐一讀取查詢範圍內的每個元素。

單點更新

若把 \(A_1\) 從 \(40\) 改成 \(30\)，只需更新該葉節點，再沿著通往根節點的路徑重新計算：

葉節點 \([1,1]\)：\(40\to30\)
父節點 \([0,1]\)：\(\gcd(20,30)=10\)
根節點 \([0,3]\)：\(\gcd(10,20)=10\)

右側 \([2,3]\) 的 GCD 仍是 \(20\)，沒有受到這次修改影響，因此不必重算。

時間與空間複雜度

令 \(n\) 為陣列長度，樹高為 \(O(\log n)\)。基本線段樹每個內部節點只需合併左右子節點的摘要。

操作	節點工作量	合併操作為 \(O(1)\)	維護 GCD 時
建樹	\(n\) 個葉節點、\(n-1\) 次合併	\(O(n)\)	\(O(nB)\)
區間查詢	\(O(\log n)\) 個相關節點	\(O(\log n)\)	\(O(B\log n)\)
單點更新	根到葉的一條路徑，\(O(\log n)\) 層	\(O(\log n)\)	\(O(B\log n)\)
空間	\(O(n)\) 個節點	\(O(n)\)	\(O(n)\)

\(B\) 表示陣列中最大整數的位元數。使用 Euclidean algorithm 計算一次 GCD，最壞需要 \(O(B)\) 次除法，因此 GCD 線段樹的建樹、查詢和更新成本會比只計算合併次數多一個 \(B\) 因子。若把一次 GCD 當作單一基本操作，常見簡寫就是建樹 \(O(n)\)、查詢與更新 \(O(\log n)\)。

若有 \(q\) 次區間查詢與 \(u\) 次單點更新，建樹後需要 \(O((q+u)\log n)\) 次摘要合併；計入 GCD 成本則為 \(O((q+u)B\log n)\)。

和每次重新掃描比較

若每次查詢都逐一計算區間內的 GCD，最壞需要掃過 \(n\) 個值；做 \(q\) 次查詢約需 \(O(qn)\) 次 GCD 合併。線段樹先花 \(O(n)\) 次合併建樹，再以 \(O(\log n)\) 次合併回答每次查詢或更新：

做法	\(q\) 次區間查詢、\(u\) 次單點更新的合併次數
每次掃描查詢區間（最壞長度為 \(n\)）	\(O(qn)\)
線段樹	\(O(n+(q+u)\log n)\)

例如 \(n=q=100{,}000\) 且沒有更新，重複掃描的最壞量級約為 \(10^{10}\) 次合併；線段樹約為 \(n+q\log_2 n\approx1.8\times10^6\) 次合併。這是操作數量的量級比較，不是實際執行秒數；若把每次 GCD 的成本也算進去，兩邊都還要乘上 \(O(B)\)。

為什麼要建這棵樹？

如果只需要算一次整個陣列的 GCD，逐項掃描就能在 \(O(nB)\) 時間完成，沒有必要先建線段樹。線段樹的好處在於資料會持續被查詢或更新時，不必每次重新掃過整段陣列。

GCD 有結合律：

\gcd(a,\gcd(b,c))=\gcd(\gcd(a,b),c)

不過 GCD 沒有如加法般的減法反運算，不能只靠兩個前綴 GCD 還原任意子區間的 GCD。線段樹則把查詢範圍拆成數個已儲存的小區間，再合併答案。