稀疏表 (Sparse Table)

引言：「零延遲」查詢

想像你有一組固定的數據，比如歷史天氣紀錄。你需要回答成千上萬個問題，比如：「第 X 天到第 Y 天之間的最低氣溫是多少？」

如果數據永不改變，為什麼還要滿足於 $O(\log N)$（線段樹）呢？ 稀疏表 (Sparse Table) 利用動態規劃預計算重疊區間，允許她在常數時間 $O(1)$ 內回答任何區間最值查詢 (RMQ)。

演算法要解決什麼問題？

• 輸入： 一個靜態陣列（不允許更新）。
• 輸出： 任意區間 [L, R] 內的最小值或最大值。
• 承諾： 理論上最快的查詢速度 ($O(1)$)。

核心思想 (直覺版)

邏輯就是 「倍增」：

1. 預計算所有長度為 1, 2, 4, 8, …（2 的冪）的區間的最小值。
2. 將其儲存在表 st[i][j] 中，含義為：「從索引 i 開始，長度為 $2^j$ 的區間最小值」。
3. 重疊的魔力： 任何長度的區間 [L, R] 都可以被 兩個重疊的、長度為 2 的冪的區間完全覆蓋。例如，長度為 7 的區間可以被兩個長度為 4 的重疊區間覆蓋。
4. 因為 min(A, B) 操作即使 A 和 B 有重疊，結果也是正確的，所以我們只需取這兩個預計算值的最小值。

演算法是如何工作的？

1. 預處理： 使用動態規劃：st[i][j] = min(st[i][j-1], st[i + 2^{j-1}][j-1])。耗時 $O(N \log N)$。
2. 查詢：
   • 計算 $k = \lfloor \log_2(R - L + 1) floor$。
   • 結果 = min(st[L][k], st[R - 2^k + 1][k])。

典型業務場景

• ✅ 歷史數據分析： 在固定的時間序列中查詢最值（例如：「2023 年的最大 CPU 負載」）。

• ✅ LCA (最近公共祖先)： 尋找樹中 LCA 的標準做法是將樹轉換為陣列，然後使用稀疏表進行 RMQ。

• ✅ 字串演算法： 在後綴陣列中尋找兩個子串的最長公共前綴 (LCP)。

• ❌ 動態數據： 如果陣列中即使只有一個元素發生改變，你也必須重新執行整個 $O(N \log N)$ 的預處理。對於動態數據，請改用 線段樹。

性能與複雜度總結

• 查詢： $O(1)$。
• 預處理： $O(N \log N)$。
• 空間： $O(N \log N)$，用於儲存倍增表。

小結：一句話記住它

「稀疏表是靜態數據的『速度狂人』。她透過預計算 2 的冪次區間，利用重疊特性實現了區間最值的一步查詢。」