st表算法

ST表算法，全稱Sparse-Table算法，是由Tarjan提出的一種解決RMQ問題（區間最值）的強力算法。這種算法的離線預處理時間複雜度為θ(nlogn)，線上查詢時間複雜度為θ(1)，因此是一種非常高效的算法。ST表的套用場合有一定的限制，它只能處理靜態區間最值，不支持在預處理後對值進行修改。一旦修改，整張表便要重新計算，時間複雜度較高。動態最值問題可以通過使用線段樹、樹狀數組等數據結構來維護。

ST表的預處理部分的核心思想是倍增。設st[i][j]表示從第i個數起向後連續2^j個數中的最小值（或最大值），其中2^j個數包括第i個數本身。轉移方程為：

st[i] = 第i個數

st[i][j] = min{ st[i][j-1], st[i+(1<

查詢時，首先找到一個值k，使得2^k不超過查詢區間長度。然後找兩個長度為2^k的區間，一個以查詢區間的左端點為左端點，一個以查詢區間的右端點為右端點。這兩個小區間一定覆蓋了整個大區間。查詢的結果就是這兩個小區間最小值中的最小值（或最大值）。

例如，假設每次查詢的左右端點分別為le和ri，我們可以找到兩個區間st[le][k]和st[ri-(1<