轉(zhuǎn)載于：http://blog.csdn.net/xuzengqiang/article/details/7350465

RMQ算法全稱為(Range?Minimum/Maximum?Query)意思是給你一個(gè)長度為n的數(shù)組A,求出給定區(qū)間的最值的下標(biāo)。當(dāng)然我們可以采用枚舉，但是我們也可以使用線段樹來優(yōu)化，復(fù)雜度為(nlogn)，但是最好的辦法是采用Sparse_Table算法，簡稱ST算法。他能在進(jìn)行(nlogn)的預(yù)處理后達(dá)到n(1)的效率。下面來分析下最大值和最小值，都要用到DP的思想。

最小值(Mininun)：我們可以用F(i,j)表示區(qū)間[i,i+2^j-1]間的最小值。我們可以開辟數(shù)組來保存F(i,j)的值，例如:F(2,4)就是保存區(qū)間[2,2+2^4-1]=[2,17]的最小值。那么F(i,0)的值是確定的,就為i這個(gè)位置所指的元素值，這時(shí)我們可以把區(qū)間[i,i+2^j-1]平均分為兩個(gè)區(qū)間，因?yàn)閖>=1的時(shí)候該區(qū)間的長度始終為偶數(shù)，可以分為區(qū)間[i,i+2^(j-1)-1]和區(qū)間[i+2^(j-1)-1,i+2^j-1]，即取兩個(gè)長度為2^(j-1)的塊取代和更新長度為2^j的塊，那么最小值就是這兩個(gè)區(qū)間的最小值的最小值，動(dòng)態(tài)規(guī)劃為：F[i,j]=min(F[i,j-1],F[i+2^(j-1),j-1]).同理:最大值就是F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1]).

現(xiàn)在求出了F[i,j]之后又是怎樣求出最大值或者最小值的，怎么轉(zhuǎn)換為o(1)這種算法的~這就是ST算法：

這個(gè)時(shí)候詢問時(shí)只要取k=ln(j-i+1)/ln2即可，那么可以令A(yù)為i到2^k的塊，和B為到2^k結(jié)束的長度為2^k的塊;那么A，B都是區(qū)間[i,j]的子區(qū)間，所以即求A區(qū)間的最小值和B區(qū)間的最小值的最小值。這個(gè)時(shí)候動(dòng)態(tài)規(guī)劃為：RMQ(i,j)=min(F[i,k],F[j-2^k+1,k]);

log2的求法：

Log[0] = -1; for(int i = 1;i <M;i++)Log[i] = ((i&(i-1)) == 0)?Log[i-1]+1:Log[i-1];RMQ：

void RMQ(int n) {int i,j;int m=Log[n];for(i=1;i<=n;i++)dp_min[i][0]=dp_max[i][0]=dis[i];//dis代表原數(shù)列for(j=1;j<=m;j++){for(i=1;i<=n+1-(1<<j);i++){dp_max[i][j]=max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);dp_min[i][j]=min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);}} }最小值：int lcp(int x,int y) {int m=Log[y-x+1];return min(dp_min[x][m],dp_min[y+1-(1<<m)][m]); }最大值

int lcp(int x,int y) {int m=Log[y-x+1];return max(dp_max[x][m],dp_max[y+1-(1<<m)][m]); }

轉(zhuǎn)載于:https://www.cnblogs.com/mypsq/p/4348112.html

總結(jié)

以上是生活随笔為你收集整理的RMQ求区间最值 nlog(n)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。