RMQ（range ?minimum/maximum query）即查詢區(qū)間最大最小值。

對于求區(qū)間最大最小值，我們自然而然就想到了一個O（n）時間復(fù)雜度的算法，但是如果詢問有很多呢？這樣必然超時。當(dāng)然我們可以用線段樹來解，使得每一次查詢的時間降到log(n)，但是對于RMQ算法，只要我們做了些預(yù)處理，之后的查詢我們僅需要O(1)的時間。 Sparse_Table算法是解決RMQ問題的一類較好的算法， 屬于一種在線算法，至于什么叫在線什么叫離線，先簡單介紹一下。

在線算法： 在計算機科學(xué)中，一個在線算法是指它可以以序列化的方式一個個的處理輸入，也就是說在開始時并不需要已經(jīng)知道所有的輸入。

離線算法： 在開始時就需要知道問題的所有輸入數(shù)據(jù)，而且在解決一個問題后就要立即輸出結(jié)果。例如， 選擇排序 在排序前就需要知道所有待排序元素，然而 插入排序 就不必了。

簡單的概括一下 在線算法就是說程序先把預(yù)處理工作做好，對于之后的查詢，可以很快給你答復(fù)。離線算法就是你先把需求告訴程序，他一次性給你解決 。

好了，下面來講解 Sparse_Table 算法

1.求最值數(shù)組

Sparse_Table 算法的預(yù)處理就是一個動態(tài)規(guī)劃的思想。

設(shè)數(shù)組maxn[i][j] 表示給定的數(shù)組從下標(biāo)i開始，長度為2^j的區(qū)間最大值(最小值一樣)也就是arr[i]----arr[i+2^j-1]這個區(qū)間的最大值。

于是我們可以寫出這樣一個動態(tài)轉(zhuǎn)移方程maxn[i][j] = max(maxn[ i ][ j-1 ],maxn[ i+2^(j-1) ][ j-1 ]) 看懂了么？

其實就是把區(qū)間【i ，i+2^j -1】分成兩段，一段是【i，i+2^(j-1)-1】 和【i+2^(j-1)，i+2^j】 (一直記住二維數(shù)組后面一維表示的是區(qū)間的長度2^j)

那么對于maxn[i][j]當(dāng)j等于0，也就是區(qū)間長度為1的最大值顯然就有maxn[i][0] = arr[i];

到此我們就可以寫出 Sparse_Table 的預(yù)處理部分了

?

    void getbestarr(int n)//n為給定的數(shù)組的長度

{

     int tem = (int)floor(log2((double)n));//因為區(qū)間的最長長度是2^tem==n嘛

   for(int i=1;i<=n;i++)

        minn[i][0]= maxn[i][0] = arr[i];

    for(int j=1;j<=tem;j++) //下標(biāo)從1開始

     for(int i=1;i+(1<<j)-1<=n;i++)

    {

         maxn[i][j] = max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);  //最大值

         minn[i][j] = min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);  //最小值

    }

}
  

我們看看這個動態(tài)規(guī)劃方程是怎么求解這個maxn,minn數(shù)組的

?

要求區(qū)間長度為2的肯定要先求出區(qū)間長度為1的嘛 ?比如區(qū)間[1,2]只要在區(qū)間[1,1] ? [2,2]中取最值嘛 長度為4的肯定要先算出長度為2的嘛 比如求區(qū)間[6,9]的最值只要在區(qū)間[6,7] [8,9]中取最值嘛。。。。。。

所以最外層的循環(huán)就肯定是區(qū)間的長度2^j次方咯 里面的循環(huán)應(yīng)該都看得懂吧。

2.查詢

這個最值區(qū)間的數(shù)組求出來了，下面就是查詢了?

比如要查詢區(qū)間[a,b]的最值 ?怎么求呢？

注意到我們的最值數(shù)組存的都是區(qū)間長度為2^k(k=0,1,2,3.....)次方的最值

所以對于區(qū)間[a,b] 我們肯定要劃分為兩個區(qū)間長度是2^x ?2^y的區(qū)間才可以直接利用我們得到的最值數(shù)組來求最值嘛

這里有兩個未知數(shù)不好求，我們可以直接取k，對于k滿足a+2^k-1=b ?k=log2(b-a+1) (注意這里不是a+2^k=b 還是那句話，始終記得2^k是區(qū)間的元素的個數(shù)) 那么區(qū)間a,b的最大值不就是max(maxn[a][k],maxn[b-2^k+1][k])比如對于區(qū)間長度為4的[3,6]求出k==2 于是最大值就是區(qū)間max（【3,6】，【3,6】）當(dāng)然我們不能能保證log2(a-b+1)就一定能得到一個整數(shù)，但是這不要緊，比如對于區(qū)間長度為5的【3,7】我們對log2(7-3+1)取整得到2，于是最大值就在

max(【3,6】，【4,7】），max函數(shù)里面前面那個maxn[a][k]就保證了我們的求最值的區(qū)間以a開始，后面那個maxn[b-2^k+1][k]就保證了我們必然能夠以b為尾

?

    int query(int a,int b,bool getwhat)//getwhat表示你是想取最大還是最小

{

   int k = log2(b-a+1);

   if(getwhat)

   return max(maxn[a][k],maxn[b-(1<<k)+1][k]);

   else

     return min(minn[a][k],minn[b-(1<<k)+1][k]);

}
  

?

?

RMQ問題