本文主要是介绍Vision_数据结构_RMQ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
///定义：/*
RMQ算法，是一个快速求区间最值的离线算法，
预处理时间复杂度O（n*log(n)），查询O(1)，所以是一个很快速的算法，
当然这个问题用线段树同样能够解决。
*/
///代码：
/*
**name:RMQ
**function:求区间最值
**输入参数:区间左右边界
**输出参数：返回最值
**复杂度：O(n*log(n))
*/
#include <iostream>
#define MAXN 100
using namespace std;
int a[MAXN];
int mx[MAXN][MAXN],mi[MAXN][MAXN],n;
void rmq_init(int ok){for(int i = 1;i<=n;i++){mx[i][0] = mi[i][0] = a[i];}for(int j = 1;(1<<j)<=n;j++){for(int i = 1;i+(1<<j)-1<=n;i++){if(ok)mx[i][j]= max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);else mi[i][j] = min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);}}
}
int rmq(int l,int r,int ok){/*那么查询的时候对于任意一个区间 l -- r ，我们同样可以得到区间差值 len = （r - l + 1）。那么我们这一用小于2^k<=len，的 k 把区间分成可以交叉的两部分l 到 l+2^（k）- 1, 到 r -(1<<k)+1 到 r 的两部分，很easy的求解了。*/int k = 0;while(1<<(k+1)<=r-l+1)k++;int ans1 = max(mx[l][k],mx[r-(1<<k)+1][k]);int ans2 = min(mi[l][k],mi[r-(1<<k)+1][k]);if(ok)return ans1;else return ans2;
}
int main(){int ok ;cin>>n>>ok;for(int i = 1;i<=n;i++)cin>>a[i];rmq_init(ok);int l,r;cin>>l>>r;cout<<rmq(l,r,ok)<<endl;return 0;
}///扩展：
/*
（1）问题：给出n个数ai，让你快速查询某个区间的的最值。
（2）算法分类：DP+位运算
（3）算法分析：这个算法就是基于DP和位运算符，
我们用dp[i][j]表示从第 i 位开始，到第 i + 2^j -1 位的最大值或者
最小值。那么我求dp[i][j]的时候可以把它分成两部分，
第一部分从 i 到 i + 2 ^(j-1)-1 第二部分从 i + 2 ^( j-1 )
到 i + 2^j - 1 次方，其实我们知道二进制数后一个是前一个的二倍，
那么可以把 i --- i + 2^j 这个区间 通过2^(j-1) 分成相等的两部分，
那么转移方程很容易就写出来了。
（4）转移方程：mm[i][j]=max(mm[i][j-1],mm[i+(1<<(j-1))][j-1]);
*/
这篇关于Vision_数据结构_RMQ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
