RMQ问题(ST算法)
admin
2023-02-14 14:20:03
0次

RMQ是询问某个区间内的最大值或最小值的问题,ST算法可以求解RMQ问题.ST算法通常用在要 多次询问某一些区间的问题中,相比于线段树,它的程序实现更加简单,运行速度更快,它可以做到O(nlogn)的预处理,O(1)回答每个问题.使用ST算法的条件是没有修改操作,因此它适用于没有修改操作并且访问次数较多(10^6级别甚至更大)的情况.

1.预处理

ST算法的原理实际上是动态规划,首先要知道f数组的含义,f[i][j]中i表示左边端点,j表示2^j个长度, 因此f[i,j]表示的是区间为[i,i+2^j-1]这个范围内的最大值,也就是以a[i]为起点连续的2^j个数的最大值.由于元素个数为2^j个,所以从中间平均分成两部分,每一部分的个数都为2^(j-1);假设f[6][3]分为f[6][2]和f[10][2],如下图所示,
RMQ问题(ST算法)
整个区间的最大值一定是左右两部分最大值的较大者,满足动态规划的最优化原理,分析得f数组的状态转移方程为f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]).

for(int j = 1;(1<

2.询问

当要访问区间[L,R]的最大值,需要知道区间的长度len,mn数组存放的是小于等于一定长度len的最大的2的幂次,若要访问区间[5,10]的最大值,则要先计算出men[len]的值,那么区间[5,10]=[5,8]U[7,10].
RMQ问题(ST算法)

代码实现

//对于一定长度的区间len,mn[len]表示小于等于len的最大的2的幂次 
   for(int len = 1;len <= n;++len)
   {
     int k = 0;
     while(1<<(k+1) <= len)
     k++;
     mn[len] = k;
   }

3.求区间[x,y]最大值

int k = mn[R - L + 1];
ans = max(f[L][k],f[R-(1<

代码实现

#include
using namespace std;
const int maxn=1e6+5; 
int f[maxn][25];
int mn[maxn];
int a[maxn];
int m,n;
void rmq_init()
{
  //初始化所有长度为1的区间的最大值 
  for(int i = 1;i <= n;i++)    
  f[i][0] = a[i];

  for(int j = 1;(1<>n;
  for(int i = 1;i <= n;i++)
  cin>>a[i];
  rmq_init();
  int L,R;
  cin>>m;
  for(int i = 1;i <= m;i++)
  {
    cin>>L>>R;
    cout<

结果截图
RMQ问题(ST算法)

上一篇：Python中logging模块的操作

下一篇：关于Django创建模型时，django.db.utils.OperationalError错误

相关内容

热门资讯

德国总理：美国正在被伊朗羞辱 德国之声4月27日报道，德国总理默茨在访问一所学校时表示，在当前的持续冲突中，伊朗领导层正试图羞辱美...
理响中国｜“长”歌以行，风云激... 光阴如梭，东方潮阔。这里是中国的长三角，世界的长三角。无论过去、现在还是未来，这片土地都因时代而生，...
白宫：特朗普及其国安团队开会讨... 新华社华盛顿4月27日电 美国白宫新闻秘书莱维特27日在记者会上证实，总统特朗普及其国家安全团队当天...
人民日报刊文：日本放开杀伤性武... 日本放开杀伤性武器出口推高地缘冲突风险（国际论坛）常思纯《人民日报》（2026年04月28日 第 0...
医疗保障法草案二审：明确生育保... 满足多样化健康保障需求本报记者 彭 波4月27日，医疗保障法草案二审稿提请十四届全国人大常委会第二十...
天津一景区发生自转旋翼机事故1... 澎湃新闻记者 吕新文中国民用航空华北地区管理局4月22日公布《豪客通航“10•1”天津长芦汉盐旅游区...
卡塔尔埃米尔与美国总统特朗普通... 当地时间24日，卡塔尔埃米尔塔米姆与美国总统特朗普通电话，重点就中东地区局势以及伊朗与美国谈判问题交...
男子30年前被扣押2859克黄... 澎湃新闻记者 王鑫家住辽宁省大连市的潘永嘉近日向澎湃新闻反映称，三十年前，他在大连周水子机场被盖州市...
商务部：取消反制欧盟两家金融机... 中华人民共和国商务部令二〇二六年 第1号鉴于欧盟已取消对中国两家金融机构的制裁措施，现公布《关于取消...
过去24小时共有5艘船只通过霍... 总台记者当地时间24日获悉，过去24小时内，共有5艘船只通过霍尔木兹海峡，其中包括一艘伊朗油轮。（总...