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

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

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

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

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

好了，下面來(lái)講解 Sparse_Table 算法

1.求最值數(shù)組

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

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

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

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

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

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

?

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

{

     int tem = (int)floor(log2((double)n));//因?yàn)閰^(qū)間的最長(zhǎng)長(zhǎng)度是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開(kāi)始

     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]);  //最小值

    }

}
  

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

?

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

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

2.查詢(xún)

這個(gè)最值區(qū)間的數(shù)組求出來(lái)了，下面就是查詢(xún)了?

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

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

所以對(duì)于區(qū)間[a,b] 我們肯定要?jiǎng)澐譃閮蓚€(gè)區(qū)間長(zhǎng)度是2^x ?2^y的區(qū)間才可以直接利用我們得到的最值數(shù)組來(lái)求最值嘛

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

max(【3,6】，【4,7】），max函數(shù)里面前面那個(gè)maxn[a][k]就保證了我們的求最值的區(qū)間以a開(kāi)始，后面那個(gè)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問(wèn)題