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

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