首页 / 算法 / RMQ-ST算法的理解与实现(C++)

RMQ-ST算法的理解与实现(C++)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了RMQ-ST算法的理解与实现(C++)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2204字，纯文字阅读大概需要4分钟。

内容图文

RMQ-ST的含义

技术分享

RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。ST算法（Sparse Table），ST（Sparse Table）算法是一个非常有名的在线处理RMQ问题的算法（在线算法指用户每输入一个查询便马上处理一个查询），它可以在O(nlogn)时间内进行预处理，然后在O(1)时间内回答每个查询。

预处理

设a[i]表示需要求区间最值的数列，f[i][j]表死从第i个数起连续2^j个数中的最大值。

则很容易得到状态转移方程：f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1])

实现代码： 

             1
            void rmq(int n)    //n为a序列的长度 2{
 3for(int j=1;j<=20;j++)   //注意是外层循环j嵌套内层i循环 4for(int i=1;i<=n;i++)
 5if(i+(1<<(j-1))-1<=n)
 6    {
 7         smin[i][j]=min(smin[i][j-1],smin[i+(1<<(j-1))][j-1]); //更新最小值 8         smax[i][j]=max(smax[i][j-1],smax[i+(1<<(j-1))][j-1]);//更新最大值 9    }
10 }

 

先更新所有长度为f[i][0]即1个元素，然后通过2个1个元素的最值获得所有长度为f[i][1](即两个元素的最值)，再到3个、4个……依次类推更新

查询

若查询的区间为[i][j]，因为该区间的长度为j-i+1，所以可以取k=log2(j-i+1),假设所求的为最大值则易得maxn=max(f[i][k],f[j-(2^k)+1][k]);

不妨举个例子假设a[13]={5,1,8,1,6,4,2,9,7,4,1,13,3},假设需要查询的是i=7到j=13这个区间，log2(13-7+1)=2,则可以知所求区间最大值=max(f[7][2],f[13-(22)+1][2])=13,

可以看出f[7][2]表示的是7到10这4个位置的最大值，而f[13-(22)+1][2]表示的是10到13这4个位置的最大值，两者的最大值即7到13这个区间的最大值，很神奇吧！！！聪明的读者一定会注意到，f[i][k]和f[j-(2^k)+1][k]会有交集，但聪明的你又会马上明白就算有交集也并不会影响最值(反而如果没有交集，便不能保证最值的准确性)，自己思考一下吧！

            1
            int k=log2(l-r+1);//(int)((log(l-r+1))/log(2.0));2int q=max(smax[r][k],smax[l-(1<<k)+1][k]),w=min(smin[r][k],smin[l-(1<<k)+1][k]);

 

 

模板题

地址 https://www.luogu.org/problem/show?pid=1816

标准的rmq-st模板题，可以去则、尝试做一下

#include<iostream>
#include<cstdio>
#include<cmath>
usingnamespace std;
int a[100005][20],m,n;
inline int getint()                    //读入优化{
    int a=0;char x=getchar();bool f=0;
    while((x<‘0‘||x>‘9‘)&&x!=‘-‘)x=getchar();
    if(x==‘-‘)f=1,x=getchar();
    while(x>=‘0‘&&x<=‘9‘)
    {a=a*10+x-‘0‘;x=getchar();}
    return f?-a:a;
}
void rmq_st(int n)                //预处理，st表{
    for(int j=1;j<=20;j++)
    for(int i=1;i<=n;i++)           //思考为什么外循环j套i，而不是外循环i套jif(i+(1<<j)-1<=n)
    a[i][j]=min(a[i][j-1],a[i+(1<<(j-1))][j-1]);   //原因在于每个区间更新都是由1个点开始慢慢增加区间范围}
int main()
{
    m=getint();n=getint();
    for(int i=1;i<=m;i++)a[i][0]=getint();   //读入数据，对于每个点开始时最小值就是它本身    rmq_st(m);
    while(n--)
    {
        int l=getint(),r=getint(),k=log2(r-l+1);
        printf("%d ",min(a[l][k],a[r-(1<<k)+1][k]));        //查询时注意思路     }
    return0;
}

 

原文：http://www.cnblogs.com/five20/p/7531644.html

内容总结

以上是互联网集市为您收集整理的RMQ-ST算法的理解与实现(C++)全部内容，希望文章能够帮你解决RMQ-ST算法的理解与实现(C++)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1065977.html

来源：【匿名】