0%

关于RMQ的总结

RMQ是英文Range Maximum(Minimum) Query的缩写,顾名思义是用来求某个区间内的最大值或最小值,通常用在要多次询问一些区间的最值的问题中。(资料)

首先,RMQ的原理也是动态规划,需要预先处理。优点在于速度快,但缺点也很明显,就是局限于静态,不同于胜者树。

对于一段区间[L,R],我们可以将其划分成两个区域,如图所示:

他不见了。

那么,求这两个区域的最大值,这两个区域的最大值的最大值,不就是区间[i..j]的最大值吗?因此这两个区域就是子问题了。

而至于k,若长度len=j-i+1,那么要使得2k<len≤2k+1。当然,求k,我们可以开一个数组Log,Log[i]表示长度为i时,k为多少。

那么,我们设F[i][k]表示第i为后2k的数中,最大值是多少。这样,

他不见了。

给出区间x和y,就可以直接求出区间[x..y]的最大值为

他不见了。

他不见了。

所以,这是一个区间DP,以长度划分阶段,类似于石子归并。

【程序】

```c++
#include
using namespace std;

ifstream fin(“RMQ.in”);
ofstream fout(“RMQ.out”);

#define maxn 10000
#define max_Log 100

int N,M;
int num[maxn],Log[maxn];
int F[maxn][max_Log];

int perpare() {
int k=0 ,now=1;
for (int i=1; i<=N; ++i) {
if (i == (now<<1)) {
k++;
now<<=1;
Log[i]=k;
}
else
Log[i]=k;
}
}

int work() {
for (int i=1; i<=N; ++i)
F[i][0]=num[i];

for (int k=1; k<=Log[N]; ++k)
    for (int i=1; i<=N; ++i)
        F[i][k]=max(F[i][k-1],F[i+(1<<(k-1))][k-1]);//状态转移方程

}

int solve(int x, int y) {
int tmp=Log[y-x+1];

return max(F[x][tmp],F[(y+1)-(1<<tmp)][tmp]);

}

int main() {
fin >> N >> M;
for (int i=1; i<=N; ++i)
fin >> num[i];

perpare();//用数组Log[i]计算得出log2i的值

work();//预处理F数组

for (int t=0; t!=M; ++t) {
    int i ,j;
    fin >> i >> j;
    fout << solve(i,j) << endl;//直接解决
}

return 0;

}

Thank you so much.