這篇文章講RMQ(Range Minimum/Maximum Query)算法。 RMQ:即區(qū)間最值查詢。對(duì)于一個(gè)長(zhǎng)度為n的數(shù)列A，詢問關(guān)于數(shù)列A中下標(biāo)在i，j間的最小或最大值。下面將介紹解決這兩個(gè)問題比較高效的算法。 RMQ算法：最容易想到的解決方案是遍歷，復(fù)雜度是O(n)。但當(dāng)數(shù)據(jù)量非常大且查詢很頻繁時(shí)，該算法無法在有效的時(shí)間內(nèi)查詢出正解。本篇文章將介紹一種比較高效的在線算法（ST算法）解決這個(gè)問題。所謂在線算法，是指用戶每輸入一個(gè)查詢便馬上處理一個(gè)查詢。該算法一般用較長(zhǎng)的時(shí)間做預(yù)處理，待信息充足以后便可以用較少的時(shí)間回答每個(gè)查詢。ST（Sparse Table）算法是一個(gè)非常有名的在線處理RMQ問題的算法，它可以在O(nlogn)時(shí)間內(nèi)進(jìn)行預(yù)處理，然后在O(1)時(shí)間內(nèi)回答每個(gè)查詢。 ①預(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時(shí)，分成[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)的順序，會(huì)發(fā)現(xiàn)j在外層，i在里層。這是由于動(dòng)態(tài)轉(zhuǎn)移方程的意義所限制，請(qǐng)讀者自行探索…… ②查詢 假如要查詢[m,n]的最大/小值，那么先求出一個(gè)最大的k。使k滿足2^k<=(n-m+1)。于是我們可以將[m,n]分成兩個(gè)（部分重疊的）長(zhǎng)度為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]);