rmq

RMQ (Range Minimum/Maximum Query)問題是指：對於長度為n的數列A，回答若干詢問RMQ(A,i,j)(i,j<=n)，返回數列A中下標在i,j里的最小(大）值，也就是說，RMQ問題是指求區間最值的問題。

基本介紹

• 中文名：RMQ
• 外文名：RMQ
• 分類：計算機求區間最值算法
• 時間複雜度：O(N)~O(logN)
• 主要思想：分治、倍增、動態規劃

簡介

主要方法及複雜度如下：

1、樸素（即搜尋），O(n)-O(qn) online。

2、線段樹，O(n)-O(qlogn) online。

3、ST（實質是動態規劃），O(nlogn)-O(q) online。

ST算法（Sparse Table），以求最大值為例，設d[i,j]表示[i,i+2^j-1]這個區間內的最大值，那么在詢問到[a,b]區間的最大值時答案就是max(d[a,k], d[b-2^k+1,k])，其中k是滿足2^k<=b-a+1(即長度)的最大的k,即k=[ln(b-a+1)/ln(2)]。

d的求法可以用動態規劃，d[i, j]=max(d[i, j-1],d[i+2^(j-1), j-1])。

4、RMQ標準算法：先規約成LCA（Lowest Common Ancestor），再規約成約束RMQ，O(n)-O(q) online。

首先根據原數列，建立笛卡爾樹，從而將問題在線性時間內規約為LCA問題。LCA問題可以線上性時間內規約為約束RMQ，也就是數列中任意兩個相鄰的數的差都是+1或-1的RMQ問題。約束RMQ有O(n)-O(1)的線上解法，故整個算法的時間複雜度為O(n)-O(1)。

ST算法

來看一下ST算法是怎么實現的（以最大值為例）：

ST表 RMQ

首先是預處理，用一個DP解決。設a是要求區間最值的數列，f[i,j]表示從第i個數起連續2^j個數中的最大值。例如數列3 2 4 5 6 8 1 2 9 7 ,f[1,0]表示第1個數起，長度為2^0=1的最大值，其實就是3這個數。f[1,2]=5，f[1,3]=8，f[2,0]=2，f[2,1]=4……從這裡可以看出f[i,0]其實就等於a[i]。這樣，DP的狀態、初值都已經有了，剩下的就是狀態轉移方程。我們把f[i,j]（j≥1）平均分成兩段（因為j≥1時，f[i,j]一定是偶數個數字），從i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1為一段（長度都為2^（j-1））。用上例說明，當i=1，j=3時就是3,2,4,5 和6,8,1,2這兩段。f就是這兩段的最大值中的最大值。於是我們得到了動規方程F[i,j]=max(F[i,j-1],F[i+2^(j-1),j-1])。

接下來是得出最值，也許你想不到計算出f有什麼用處，一般要想計算max還是要O(logn)，甚至O(n)。但有一個很好的辦法，做到了O(1)。還是分開來。如在上例中我們要求區間[2,8]的最大值，就要把它分成[2,5]和[5,8]兩個區間，因為這兩個區間的最大值我們可以直接由f[2,2]和f[5,2]得到。擴展到一般情況，就是把區間[l,r]分成兩個長度為2^n的區間（保證有f對應）。直接給出表達式：

k:=trunc(ln(r-l+1)/ln(2));

ans:=max(F[l,k],F[r-2^k+1,k]);

這樣就計算了從l開始，長度為2^k的區間和從r-2^k+1開始長度為2^k的區間的最大值（表達式比較繁瑣，細節問題如加1減1需要仔細考慮），二者中的較大者就是整個區間[l,r]上的最大值。

標準算法

建立笛卡爾樹

數組A[0,N-1]的笛卡爾樹C是這樣一棵二叉樹：當N=0，它是一棵空樹，否則它的根節點是A中的一個最小元素A[i]（並以這個最小元素的下標i標記），而左右子樹分別是A[0,i-1]和A[i+1,N-1]的一棵笛卡爾樹。注意如果A中有相等的元素，則A的笛卡爾樹不一定唯一，但在這裡我們限定所用的最小元素為在數組中最先出現者，在此限制下笛卡爾樹是唯一的。

容易看出，數組A在閉區間[l,r]上的最小值等同於笛卡爾樹C中下標為l和r的兩個頂點的最近公共祖先（LCA）的值。由此，RMQ問題可以轉化為LCA問題。下面說明如何在O(n)時間內實現這一轉化。

我們將要將A的元素依次插入笛卡爾樹C。每次插入都可能使樹的形態發生變化。為了在O(N)的時間內完成整個插入過程，考慮C的右鏈，即根結點、根結點的右兒子、根結點的右兒子的右兒子……組成的鏈。注意這些元素的下標和值都是遞增的。下標最大，即將要插入的元素A[i]一定是新樹右鏈的最後一個元素。原來的右鏈中，值比A[i]大的元素在新樹中不再屬於右鏈，這些元素組成的鏈成為A[i]的左子樹的右鏈；原來右鏈中的其它元素加上A[i]組成了新的右鏈。初看起來，尋找分界點的最佳方法是O(logN)時間的二分查找；但是對於整個過程來說，O(NlogN)的時間複雜度不是最優的。關鍵在於一旦一個元素比A[i]大，它就從右鏈中被永久地移除了。如果按照從後到前的順序判斷一個元素是否大於A[i]，則每次插入的時間複雜度為O(k+1)，k為本次插入中移除的右鏈元素個數。因為每個元素最多進出右鏈各一次，所以整個過程的時間複雜度為O(N)。

用一個棧結構維護右鏈元素的下標，上述過程可以很容易地實現。（見下面代碼部分）

轉化為約束RMQ

為了將LCA問題轉化為約束RMQ，我們注意到任意樹中兩個結點u和v的LCA就是在一次從樹根開始的深度優先搜尋中，在u和v之間（包括回溯時）到達的結點中層數最小的一個。為了利用這一事實，我們建立三個數組：

E[1,2*N-1]：在一次深度優先搜尋（恰好是樹的一次歐拉環遊）中每一步到達的結點。

L[1,2*N-1]：E中對應結點在樹中的層數。

H[1,N]：每個結點在E中某一次出現的下標（不妨設為第一次）。

則對任意u和v，不妨設H[u]≤H[v]（否則交換u和v），只要在L中找到[H[u],H[v]]中最小值的下標i，則E[i]就是u和v的LCA。注意到L滿足約束RMQ的條件（相鄰元素差的絕對值為1），這說明原來的LCA問題已經被轉化為約束RMQ。轉化過程顯然能在O(N)時間內完成。

約束RMQ的解法

現在仍舊用A[0,N-1]表示問題中的數列，這裡有|A[i]-A[i-1]|=1（i=1,2,...,N-1）成立。

將A分解為長度為l=[(log N)/2]的塊。設A'[i]為第i塊中的最小值，B[i]為該最小值的位置。A'[i]和B[i]的長度均為N/l， 所以用ST算法處理A'數組的時空複雜度均為O(N/l*log(N/l))=O(N/logN*(logN-logl))=O(N)。預處理之後，對任意多連續的塊進行的查詢都能在O(1)時間內實現。餘下的問題是如何進行塊內查詢。

注意到對任意一塊中的塊內查詢的結果有影響的唯一因素是塊內每相鄰兩個元素間的“升降關係”構成的序列。因為每兩個元素之間的關係只有兩種（“+1”、“-1”），而塊的長度又只有l=[(log N)/2]，所以本質不同的塊最多有2^I=O(sqrt N)種。對每種塊中所有可能的塊內查詢預處理出答案的時空複雜度是O(sqrt N*l^2)=O(N)（這裡的O(N)表示不超過線性時間）。預處理出所有塊的“類型”，並用二進制數存儲的時間複雜度是O(N)。

此後，每次查詢可以分為兩種情況：

1、塊內查詢，答案已經被預處理出，只要在數組中找到它即可。

2、塊間查詢，可以分解為2個塊內查詢，和一個A'上的RMQ，三者的時間複雜度都是O(1)。

綜上，我們給出了一個預處理時間為O(n)，查詢時間為O(1)的線上RMQ算法。

代碼

RMQ(Range Minimum/Maximum Query)問題是求區間最值問題。你當然可以寫個O(n)的（怎么寫都可以),但是萬一要詢問最值1000000遍，估計你就要掛了。這時候你可以放心地寫一個線段樹（前提是不寫錯）O（logn)的複雜度應該不會掛。但是，這裡有更牛的算法，就是ST算法，它可以做到O(nlogn)的預處理，O(1)地回答每個詢問。

ST算法，Pascal，程式片段

Read(n,q);for i:=1 to n doRead(d[i,0]);for j:=1 to Trunc(Ln(n)/Ln(2))dofor i:=1 to n-1 shl j+1 dod[i,j]:=Max(d[i,j-1],d[(i+1) shl (j-1),j-1]);for i:=1 to q dobeginRead(a,b);k:=Trunc(Ln(b-a+1)/Ln(2));rmq:=Max(d[a,k],d[(b-1) shl (k+1),k]);Writeln(rmq);end;

ST算法，Pascal，完整過程

var p,n,m,z:longint;aa,data:array[0..100001]oflongint;procedure myread;var i:longint;beginread(n,m);fori :=1 to n do read(aa[i]);z:=trunc(sqrt(n));data[1]:=maxlongint;p:=1;for i:=1 to n dobeginif aa[i]<data[p] then data[p]:=aa[i];if i mod z=0 then begin inc(p);data[p]:=maxlongint;end;end;end;procedure main;var tt1,tt2,a,b,i,j,t1,t2,min:longint;beginfor i:=1to m dobeginread(a,b);t1:=adivz+1;t2:=bdivz+1;tt1:=amodz;tt2:=bmodz;min:=maxlongint;if t1=t2 thenbeginfor j:=a to b doif min>aa[j]then min:=aa[j];write(min,'');continue;end;for j:=((t1-1)*z+tt1) to t1*z doif min>aa[j] then min:=aa[j];for j:=((t2-1)*z)to((t2-1)*z+tt2)doif min>aa[j]then min:=aa[j];for j:=t1+1 to t2-1doif min>data[j] then min:=data[j];write(min,'');end;end;beginmyread;main;end.

ST算法，C++

#include<iostream>#include<cstdio>#include<cstdlib>#include<cmath>using namespace std;int map[1000005][20];int n;void work(){    int i,j;    for(j=1;1<<j<=n;j++)    for(i=1;i+(1<<j)-1<=n;i++)//i+(1<<j)-1<=n是為了保證區間左端點不超出總數n    map[i][j]=min(map[i][j-1],map[i+(1<<j-1)][j-1]);//實質是動態規劃}int question(int z,int y){    int x=int (log(y-z+1)/log(2));//注意y-z要加一才為區間長度    return min(map[z][x],map[y-(1<<x)+1][x]);//分別以左右兩個端點為基礎，向區間內跳1<<x的最//大值; }int main(){    scanf("%d",&n);//輸入數據總數    int i,a,b,k;    for(i=1;i<=n;i++)    scanf("%d",&map[i][0]);//數據輸入加初始化，即從i開始向右走2的0次方的區間中的最大值，（注//意i到i的長度為一）。    work();//預處理    scanf("%d",&k);//輸入詢問次數k    for(i=1;i<=k;i++)        {            scanf("%d%d",&a,&b);            printf("%d\n",question(a,b));//輸出結果        }    return 0;}

ST算法，JAVA

public class RMQ{    int[] nums;    int[][] st;        public RMQ(int[] nums){        this.nums = nums;        int n = nums.length;        this.st = new int[n][(int)(Math.log(n + 1) / Math.log(2)) + 1];        RMQInit();    }        private void RMQInit(){        int n = nums.length;        for(int i = 0; i < n; i++)  st[i][0] = nums[i];                for(int j = 1; (1 << j) <= n; j++){            for(int i = 0; i + (1 << j) - 1 < n; i++){            st[i][j] = Math.max(st[i][j - 1], st[i + (1 << (j - 1) )][j - 1]);            }        }    }        public int query(int u, int v){        return RMQQuery(u, v);    }        private int RMQQuery(int u, int v){        int k = (int) (Math.log(v - u + 1) / Math.log(2));        return Math.max(st[u][k], st[v - (1 << k) + 1][k]);    }}

建立笛卡爾樹，C++

voidcomputeTree(intA[MAXN],intN,intT[MAXN])//T[i]儲存每個結點的父結點（左右子樹是無所謂的）{    intst[MAXN],i,k,top=-1;    //從空棧開始    //第i步，我們將A[i]插入棧中    for(i=0;i<N;i++)    {    //找到第一個小於等於A[i]的元素    k=top;    while(k>=0&&A[st[k]]>A[i])        k--;    //如上述，更改樹的結構    if(k!=-1)        T[i]=st[k];    if(k<top)        T[st[k+1]]=i;    //將A[i]插入棧中，並移除所有更大的元素    st[++k]=i;    top=k;    }    //棧中的第一個元素就是樹根，沒有父節點    T[st[0]]=-1;}