不是每個區間查詢都需要能改值的資料結構。當陣列建好就凍住，你該追求的不是 O(log n)，而是 O(1)。
為什麼有了線段樹還需要它？
你手上一份跑完就不再變動的資料——某天的股價序列、一份排好的成績單、預先算好的地形高度圖——然後有人要對它問上百萬次「第 L 到第 R 名裡最高分多少？」。
用線段樹當然能解，每次查詢 O(log n)。但你有沒有想過，這個 log 是白吞的？線段樹的 log 是為了支援修改才付的稅：它把區間切成一棵樹，好讓你改一個值時只需要更新一條路徑。可你的資料根本不會改，你付了維護一棵可變樹的成本，卻完全用不到那個「可變」。
這就是 Sparse Table 存在的理由。它認定一件事：如果資料靜態，那我可以把功課全做在前面。花 O(n log n) 把各種長度區段的答案預先算好，之後每次查詢只翻兩下表、比一次大小——O(1)，連那個 log 都省掉。
一句話劃清界線：
- 線段樹：資料會變，查詢 O(log n)，改值 O(log n)。
- Sparse Table：資料不變，預處理 O(n log n)，查詢 O(1)，改值——沒這功能。
核心：用 2 的冪次區段拼答案
Sparse Table 的骨架是一張二維表，table[i][k] 存的是「從 i 開始、長度剛好 2^k 的那段區間」的答案（以 RMQ 為例就是最小值）：
table[i][k] = min( arr[i .. i + 2^k - 1] )
arr = [3, 1, 4, 1, 5, 9, 2, 6]
0 1 2 3 4 5 6 7
k=0（長度 1）: [3][1][4][1][5][9][2][6] ← 就是原陣列
k=1（長度 2）: [1][1][1][1][5][2][2] ← 每相鄰 2 個取 min
k=2（長度 4）: [1][1][1][1][2] ← 每相鄰 4 個取 min
k=3（長度 8）: [1] ← 整段取 min關鍵在建表時不必真的去掃每一段。長度 4 的區間，就是兩個長度 2 的區間拼起來；長度 2 的又是兩個長度 1 的拼起來。這種「大區間用兩個半長區間拼出來」正是**倍增（binary lifting）**的思路——每一層都站在前一層的肩膀上，遞推一次就好：
public SparseTable(int[] arr) {
n = arr.length;
int maxK = (int)(Math.log(n) / Math.log(2)) + 1;
// 預先把 log2 值算好，查詢時就不用每次重算
log[1] = 0;
for (int i = 2; i <= n; i++) log[i] = log[i / 2] + 1;
// 第 0 層：長度 1 的區間就是原陣列
for (int i = 0; i < n; i++) table[i][0] = arr[i];
// 第 k 層：由第 k-1 層兩段拼出來
for (int k = 1; k < maxK; k++)
for (int i = 0; i + (1 << k) <= n; i++)
table[i][k] = Math.min(table[i][k - 1],
table[i + (1 << (k - 1))][k - 1]);
}O(1) 查詢的秘密：允許重疊
建好表以後，任意區間 [L, R] 的長度不一定剛好是 2 的冪次，怎麼辦？
答案漂亮得有點狡猾：用兩個會重疊的 2^k 區段把它蓋滿。取最大的 k 使得 2^k ≤ R − L + 1，一段從左端 L 往右鋪 2^k，另一段從右端 R 往左鋪 2^k——中間重疊沒關係。
查詢 [2, 6]，長度 5
k = floor(log2(5)) = 2，段長 2^2 = 4
左段：[2, 5] ────┐
右段： [3, 6] ─┘ ← 3~5 這段被蓋了兩次
min([2,6]) = min( table[2][2], table[3][2] )一般的資料結構最怕重複計算，這裡卻擺明讓兩段重疊。撐住這招的是一個叫**冪等性（idempotent）**的性質：min(a, a) = a。一個元素被算兩次跟算一次結果一模一樣，所以重疊區間怎麼蓋都不影響答案。
public int queryMin(int L, int R) {
int k = log[R - L + 1];
return Math.min(table[L][k], table[R - (1 << k) + 1][k]);
}整個查詢就兩次查表、一次比大小，跟區間多長完全無關。這就是 O(1) 的來源。
冪等，就是它的邊界
冪等性成就了 O(1)，但也框死了 Sparse Table 的適用範圍。看一眼求和就懂為什麼：sum 不是冪等的，重疊區間裡的元素會被加兩次，答案直接錯掉。所以區間求和該用前綴和（一樣 O(1)、還不吃 log 空間），要邊改邊查就回頭找線段樹。
能不能上 Sparse Table，就看你的操作滿不滿足「同一個值算幾次都一樣」：
| 操作 | 可用 Sparse Table | 原因 |
|---|---|---|
| 區間 min / max | ✅ | 冪等 |
| 區間 GCD | ✅ | 冪等 |
| 區間位元 AND / OR | ✅ | 冪等 |
| 區間求和 | ❌ | 非冪等，重疊會重複累加 |
| 需要邊改邊查 | ❌ | 靜態結構，建完不能動 |
複雜度攤開來對比，甜蜜點很清楚——查詢多、資料不變的場景：
| 時間 | 空間 | |
|---|---|---|
| 建表（一次性） | O(n log n) | O(n log n) |
| 單次查詢 | O(1) | — |
選型的一句話：資料會動、要區間求和，用線段樹或前綴和；資料凍住、只查冪等的 min/max/gcd，Sparse Table 是最俐落的那一把。兩者不是誰比較強，是「要不要付可變的稅」這個問題的兩個答案。
🎬 互動視覺化：區間查詢視覺化 — 動手拉一個
[L, R]，看它怎麼被兩段 2^k 區間覆蓋、重疊處為什麼不影響結果，比盯著遞推公式好懂得多。
線段樹是一輛能隨時換乘客的公車，靈活但每站都要停；Sparse Table 是資料定案後開出的特快車——不准中途上下客，換來一路不停的 O(1)。
接下來往哪走
- Segment Tree 線段樹 — 對照組：資料會變動時的區間查詢主力，用 O(log n) 換到「可修改」這件事
- Binary Lifting 倍增法 — Sparse Table 的建表本質就是倍增，同一招換到樹上就是「跳 2^k 個祖先」