搜索

AcWing 算法提高课 RMQ(区间最值查询) st表


发布时间: 2022-11-24 18:03:06    浏览次数:7 次

RMQ 又叫 st表 跳表

本质是倍增动态规划

 

 

 

 查询的时候,每次查询使用一个最大的k,使得2^k<=len(r-l+1)

然后找到[l, r]区间中前2^k和后2^k中的最大值,取最大

模板:

const int N=200010;
const int M=18;//2^M>200010

int n,m;
int nums[N];
int st[N][M];

void Init()
{
    for(int j=0;j<M;j++)//区间长度
    {
        for(int i=1;i+(1<<j)-1<=n;i++)//区间左端点
        {
            if(j==0) st[i][j]=nums[i];
            else st[i][j]=max(st[i][j-1],st[i+(1<<( j-1))][j-1]);
        }
    }
}

int Query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);//log2(len)得到len对应查询的j长度
    return max(st[l][k],st[r-(1<<k)+1][k]);
}

void YD()
{
    cin>>n;
    fore(i,1,n) cin>>nums[i];
    Init();
    cin>>m;
    fore(i,1,m)
    {
        int l,r;cin>>l>>r;
        cout<<Query(l,r)<<endl;
    }
}
 
View Code

 

免责声明 AcWing 算法提高课 RMQ(区间最值查询) st表,资源类别:文本, 浏览次数:7 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 06:03:06。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/ydUESTC/p/16803337.html