1 概述

稀疏表（Sparse Table，ST）是一種用于高效解決 靜態區間查詢（Range Query） 問題的數據結構，主要用于 可重復貢獻問題（Idempotent Range Queries），例如區間最小值（RMQ）、區間最小值（RMQ）、區間GCD等。其核心思想是 預處理+倍增思想，可以在 O(n log n) 預處理 和 O(1) 查詢 的時間復雜度下完成操作。

最后建的表如下圖所示：

2 實現原理

詳見：一種比線段樹還高效的區間算法
數據結構與算法_倍增思想（稀疏表：區間最值查詢問題）