這篇文章講RMQ(Range Minimum/Maximum Query)算法。 RMQ:即區(qū)間最值查詢。對于一個長度為n的數(shù)列A，詢問關(guān)于數(shù)列A中下標(biāo)在i，j間的最小或最大值。下面將介紹解決這兩個問題比較高效的算法。 RMQ算法：最容易想到的解決方案是遍歷，復(fù)雜度是O(n)。但當(dāng)數(shù)據(jù)量非常大且查詢很頻繁時，該算法無法在有效的時間內(nèi)查詢出正解。本篇文章將介紹一種比較高效的在線算法（ST算法）解決這個問題。所謂在線算法，是指用戶每輸入一個查詢便馬上處理一個查詢。該算法一般用較長的時間做預(yù)處理，待信息充足以后便可以用較少的時間回答每個查詢。ST（Sparse Table）算法是一個非常有名的在線處理RMQ問題的算法，它可以在O(nlogn)時間內(nèi)進(jìn)行預(yù)處理，然后在O(1)時間內(nèi)回答每個查詢。 ①預(yù)處理：預(yù)處理用DP的思想。 首先處理DP的狀態(tài)：設(shè)F[i,j]表示[i,i+2^j-1]區(qū)間的最小值。例如，F(xiàn)(0,0)表示[0,0]之間的最小值，F(xiàn)(0,2)表示[0,3]之間的最小值，F(xiàn)(2,4)表示[2,17]之間的最小值。 然后處理DP的初始化:不難看出F[i,0]就等于A[i]。 最后是DP的狀態(tài)轉(zhuǎn)移方程：將F[i,j]平均分成兩段。[i,i+2^(j-1)-1]區(qū)間為一段，[i+2^(j-1),i+2^j-1]區(qū)間為一段。例如，當(dāng)i=1,j=3時，分成[1,4]和[5,8]兩段。所以狀態(tài)轉(zhuǎn)移方程：F[i,j]=max/min(F[i,j-1],F[i+2^(j-1),j-1])。 代碼如下：

注意循環(huán)的順序，會發(fā)現(xiàn)j在外層，i在里層。這是由于動態(tài)轉(zhuǎn)移方程的意義所限制，請讀者自行探索…… ②查詢 假如要查詢[m,n]的最大/小值，那么先求出一個最大的k。使k滿足2^k<=(n-m+1)。于是我們可以將[m,n]分成兩個（部分重疊的）長度為2^k的區(qū)間:[m,m+2^k-1],[n-2^k+1,n];F[m,k]為F[m,m+2^k-1]的最大/小值，F(xiàn)[n-2^k+1,k]是[n-2^k+1,n]的最大/小值。狀態(tài)轉(zhuǎn)移方程：RMQ(i,j)=max/min(F[m,k],F[n-2^k+1,k]);