原理2　ST

ST（Sparse Table，稀疏表）算法采用了倍增思想，在O(nlogn)時間構造一個二維表之后，可以在O(1)時間在線查詢[l, r]區間的最值，有效解決在線RMQ（Range Minimum/Maximum Query，區間最值查詢）問題。

如何實現呢？設F[i, j]表示[i, i+2j-1]區間的最值，區間長度為2j。

根據倍增思想，長度為2j的區間可被分成兩個長度為2j-1的子區間，然后求兩個子區間的最值即可。遞推公式：F[i, j]=max(F[i, j-1], F[i+2j-1, j-1])。

1. ST創建

若F[i, j]表示[i, i+2j-1]區間的最值，區間長度為2j，則i和j的取值范圍是多少呢？

若數組的長度為n，最大區間長度2k≤n<2k+1，則k=，比如n=8時k=3，n=10時k=3。在程序中，k=log2(n)，也可用通用表達方式k=log(n)/log(2)，log()表示以e為底的自然對數。

算法代碼：

例如有10個元素a[1..10]={5, 3, 7, 2, 12, 1, 6, 4, 8, 15}，其查詢最值的ST如下圖所示。

F[i, j]表示[i, i+2j-1]區間的最值，區間長度為2j。

? F[1, 0]表示[1, 1+20-1]區間，即[1, 1]的最值為5，第0列為數組自身。

? F[1, 1]表示[1, 1+21-1]區間，即[1, 2]的最值為5。

? F[2, 3]表示[2, 2+23-1]區間，即[2, 9]的最值為12。

? F[6, 2]表示[6, 6+22-1]區間，即[6, 9]的最值為8。

2. ST查詢

若查詢[l, r]區間的最值，則首先計算k值，和前面的計算方法相同，區間長度為r-l+1，2k≤r-l+1<2k+1，因此k=log2(r-l+1)。

若查詢區間的長度大于或等于2k且小于2k+1，則根據倍增思想，可以將查詢區間分為兩個查詢區間，取兩個區間的最值即可。兩個區間分別為從l向后的2k個數及從r向前的2k個數，這兩個區間可能有重疊，但對求最值沒有影響。

算法代碼：

3. 算法分析

創建ST時，初始化需要O(n)時間，兩個for循環需要O(nlogn)時間，總時間復雜度為O(nlogn)。區間查詢實際上是查表的過程，計算k值后從表中讀取兩個數取最大值即可，因此查詢的時間復雜度為O(1)。一次建表，多次使用，這種查表法就是動態規劃。