【学习笔记】RMQ-Range Minimum/Maximum Query …

2019-08-26 05:37:34来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

【学习笔记】RMQ-Range Minimum/Maximum Query (区间最小/最大值)

RMQ是一类询问区间最小/最大值的问题。

这类问题一般分成两类:静态区间(无修改),动态区间(带修改)。

对于动态区间查询最大/最小,我们显然可以用线段树来解决……

那么对于静态区间查询最大/最小的问题,我们一般用ST算法解决。(显然这个我们也可以用线段树)

这个算法相比于线段树来说有以下优点:

·程序实现比较简单。

·运行速度快,常数小。

 

接下来为了解释方便,我们假设我们要查询区间的最大值。

一.ST算法的实质

  ST算法的实质是动态规划。

  现在我们有一组数a[1…n];

  我们定义f(i,j)表示从a[i]开始,向后长度为2j的区间中最大值。基于分治思想,我们可以把这段区间分为两部分,每一部分的长度恰好是2j-1

  那么显然有以下转移方程:

  f(i,j)=max(f(i,j-1),f(i+2j-1,j-1);

  这就是ST算法的实质,下面介绍ST算法的流程。

二.ST算法的流程

  1.预处理

    上面我们提到过,ST算法的实质就是动态规划。那么我们通过枚举i和j来预处理f数组,复杂度为O(nlogn)。

    状态转移方程:f(i,j)=max(f(i,j-1),f(i+2j-1,j-1);

    边界条件:f(i,0)=ai;为每个位置的元素值。

  2.询问

    如果我们要询问区间[l,r]的最大值,我们同样把这个区间分为两个部分,但这次我们将这个区间分为两个有交集区间。

    根据f数组的第二维,我们找到一个数x满足2x≤r-l+1,然后把区间分为[l,l+2x-1]和[r-2x+1,r],显然这两个区间的并集就是我们要查找的区间[l,r]。

    通过这样的处理,这两个区间的元素正好是2的正次幂,所以[l,r]区间的最大值为max(f(l,x),f(r-2x+1,x)),查询操作的复杂度是O(1)。

    

    那么我们要求区间[l,r]的最大值,有以下表达式:

    k=log2(r-l+1);

    ans=max(f[l][k],f[r-2k+1][k]);

 

通过这些我们可以发现,ST算法适用于没有修改操作并且询问次数较多的RMQ问题。

 

三.一些技巧

  我们可以用O(n)的额外时间预处理出log数组,这个过程是递推的,根据函数本身定义我们可以得到以下式子:

  log(x)=log(x/2)+1;

 

四.代码

  有N个数,M个询问,询问区间最大值:

  

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,l,r,ds[1000010],R[1000010][21];//ds即为log预处理,R表示f数组
 4 int main()
 5 {
 6     scanf("%d%d",&n,&m);
 7     ds[0]=-1;//方便递推
 8     for(int i=1;i<=n;i++)
 9     {
10         scanf("%d",&R[i][0]);
11         ds[i]=ds[i>>1]+1;
12     }
13     for(int j=1;j<=20;j++)
14     {
15         for(int i=1;i+(j<<1)-1<=n;i++)
16         {
17             R[i][j]=max(R[i][j-1],R[i+(1<<j-1)][j-1]);
18         }
19     }
20     for(int i=1;i<=m;i++)
21     {
22         scanf("%d%d",&l,&r);
23         int s=ds[r-l+1];
24         printf("%d\n",max(R[l][s],R[r-(1<<s)+1][s]));
25     }
26     return 0;
27 }
View Code

 

 


原文链接:https://www.cnblogs.com/Rakan-LoveJ/p/11384660.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:初级线段树小结

下一篇:输入输出的优化问题