RMQ—ST

原题链接

在RMQ问题中，著名的ST算法就是倍增的产物。给定一个长度为N的序列A，ST算法能够在O(NlogN)的时间的预处理后，以O(1)的时间复杂度在线回答"数列A的下标在l~r之间的最大值是多少"

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
const int N=1e5+10;
int a[N];
int dp[N][110];
int n,m;

void ST_prework()
{
    //数列在子区间[i,i]里的最大值
    for(int i=1;i<=n;i++)   dp[i][0]=a[i];
    
    int t=log(n)/log(2)+1;
    //枚举区间长度倍增类型
    for(int j=1;j<t;j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)//枚举起点
        {
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}

int ST_query(int l,int r)
{
    //计算出那么一个k，满足(2的k次<=r-l+1<2的k+1次),查找区间达到最大
    int k=log(r-l+1)/log(2);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    ST_prework();
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int k=ST_query(x,y);
        printf("%d\n",k);
    }
    return 0;
}