1. 倍增思想

????任意整數(shù)均可表示成若干個2的次冪項的和。例如，整數(shù)5，其二進(jìn)制位101，該二進(jìn)制數(shù)從右側(cè)向左，第0，2位均為1，那么 5 = 2^2 + 2^0; 整數(shù)26，其二進(jìn)制數(shù)表示為11010，該二進(jìn)制數(shù)從右側(cè)向左，第1，3，4 位均為1，那么 26 = 2^4 + 2^3 + 2^1。也就是說2的次冪項可以拼成任何一個需要的值。

????倍增，顧名思義，就是成倍的增長。如果問題的狀態(tài)空間特別大，一步一步的遞推算法復(fù)雜度太高，可以通過倍增思想，只考察2的整數(shù)次冪位置，快速縮小求解范圍，直到找到所要的解。

????例如，一顆樹中，每一個結(jié)點的祖先均比該結(jié)點大，查找4的祖先中等于 x 的祖先結(jié)點。最笨的辦法就是一個一個的向上比較祖先結(jié)點，判斷哪一個等于 x ，如果樹特別大，搜索的效率很低。雖然祖先具有有序性，但是不是順序存儲，無法得到中間結(jié)點的下標(biāo)，因此不可以采用普通的二分搜索，怎么辦呢？

????采用倍增的思想：

• ????x和當(dāng)前結(jié)點向上 2^0個結(jié)點比較，如果 x 大于該結(jié)點，則向上跳 2^0個結(jié)點；
  

• ????x和當(dāng)前結(jié)點向上 2^1個結(jié)點比較，如果 x 大于該結(jié)點，則向上跳 2^1個結(jié)點；

• ????x和當(dāng)前結(jié)點向上 2^2個結(jié)點比較，如果 x 大于該結(jié)點，則向上跳 2^2個結(jié)點；

• ????...
  

• ????x和當(dāng)前結(jié)點向上 2^k個結(jié)點比較，如果 x 小于該結(jié)點，則鎖定搜索范圍，減少增量繼續(xù)搜索：

• x和當(dāng)前結(jié)點向上 2^(k-1) 個結(jié)點比較，如果 x 小于該結(jié)點，則鎖定搜索范圍，減少增量繼續(xù)搜索：

• x和當(dāng)前結(jié)點向上 2^(k-2) 個結(jié)點比較，如果 x 大于該結(jié)點，則向上跳 2^(k-2) 個結(jié)點；

• ? ? 從當(dāng)前結(jié)點出發(fā)，繼續(xù)搜索，直至找到該結(jié)點，查找成功，或增量減為 2^0 仍不相等，查找失敗。

????也就是說， x 和當(dāng)前結(jié)點向上 2^i 個結(jié)點比較，如果 x 大于該結(jié)點，則向上跳 2^i 個結(jié)點，加大增量 2^(i+1) ,繼續(xù)比較； 如果 x 小于該結(jié)點，則減少增量 2^(i-1)，繼續(xù)比較； 直到相等返回查找成功，或增量減為 2^0仍不相等，查找失敗。

2. 稀疏表(ST)

????稀疏表（Sparse Table, ST）算法是采用倍增的思想， 在 O(n logn) 的時間構(gòu)造一個二維表之后，可以在 O(1) 的時間在線查詢區(qū)間 [ l, r ] 的最值。 ST 算法可以有效的解決在線 RMQ問題（區(qū)間最值查詢）。

????怎么實現(xiàn)呢？

????設(shè) F[i，j] 表示區(qū)間 [ i, i+2^j-1] 的最值，區(qū)間長度為 2^j , 如圖所示：

????

????根據(jù)倍增思想，區(qū)間長度為 2^j 可以分成兩個區(qū)間長度為 2^(j-1) 的子區(qū)間，然后求兩個子區(qū)間的最值即可。

????遞推公式： F[i，j] = max( F[ i, j-1], F[i + 2^(j-1),j-1])

?（1）ST 表創(chuàng)建

????F(i,j) 表示區(qū)間 [ i, i+2j-1] 的最值，區(qū)間長度為 2^j，那么 i 和 j 的取值范圍是多少呢？

????如果數(shù)組的長度 n，最大區(qū)間長度 2^k <= n <= 2^(k+1)， 則 k = [ log2?(n)?]，例如 n = 8,則 k = 3; n=10,則 k = 3。在程序中， k = log2?(n), 也可以用通用表達(dá)式 k = log(n)/log(2),其中l(wèi)og()表示以 e 為底的自然對數(shù)。

????區(qū)間長度： 2^0, 2^1, 2^2, ..., 2^k, j = 0,1, ..., k 。

????起點 i ：1, 2, ..., n-2^j +1, i = 1,2, ..., n-2^j +1。

????初始化， F[ i, j ] = a[ i ] ,表示區(qū)間 [ i, i ]?的最值，區(qū)間長度為 2^0。

?算法代碼：

????例如，有 10 個元素 a[ 1 ... 10] = { 5, 3, 7, 2, 12, 1, 6, 4, 8, 15}，其查詢最值的ST表如圖所示。 F[ i, j ] 表示區(qū)間 [ i , i+ 2^j -1 ] 的最值，區(qū)間長度為 2^j。

（2）ST表查詢

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

????查詢區(qū)間長度大于等于 2^k , 小于 2^(k+1) ， 那么根據(jù)倍增思想，可以將查詢區(qū)間分為兩個查詢區(qū)間，取兩個區(qū)間的最值即可。兩個區(qū)間分別為從l 向后的 2^k 個數(shù)，從 r 向前的 2^k 個數(shù)，這兩個區(qū)間有可能有重疊，但對求最后沒有影響。如圖所示。

????算法代碼：

（3）ST算法性能分析