RMQ问题

平面向皮卡丘 · 2019-05-15 20:20:13 · 个人记录

RMQ(Range\ Maximun/Minimun\ Problem)问题

1. 问题介绍。对于某个给定的数组，在给定的区间内求最大/小值，有多次查询，而没有修改。

2. ST算法：

1). 预处理。设a[]是原数列，f[i][j]表示第i个数起连续2^j个数中的最大值。则有状态转移方程f[i][j]=max\{f[i][j-1],f[i+2^{j-1}][j-1]\}，意思是将区间[i,i+2^j-1]平均分成两段[i,i+2^{j-1}-1]和[i+2^{j-1},i+2^j-1]，求这两段的最大值。下面是求f数组的代码。

for(int j=1;j<=LogN;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);

2).查询。 设要查询的区间为[x,y]，找到覆盖这个区间的最小幂k=log_{2}(y-x+1)。则答案就是max\{f[i][k],f[j-2^k+1][k]\}。

如何寻找最小幂。我们可以知道log_{2}d=log_{2}(d/2)+1，则可以写出下面的代码。

Log[0]=-1;
for(int i=1;i<=n;i++)
    Log[i]=Log[i>>1]+1;

下面是完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100005,LogN=30;
int Log[MAXN],f[MAXN][LogN],a[MAXN];
int n,m,x,y;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    Log[0]=-1;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=a[i];
        Log[i]=Log[i>>1]+1;
    }
    for(int j=1;j<=LogN;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    int k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        k=Log[y-x+1];
        printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k]));
    }
    return 0;
}