数据结构——RMQ

　　　RMQ

　　今天临放学前终于是学会了RMQ,特此写一篇题解来缅怀

　　RMQ是一种数据结构,用途是查询区间内最大值或最小值

或者你所要求的任意条件,主要思想是二进制的思想,其中还用到了dp的思想,

是一种非常不错的算法,在确定左右区间查询上时间复杂度优于线段树

但是NOIP并不常用,也算为后面的LCA打一个基础

　　给一道题:

　　n个数，m个询问，每次询问区间[L,R]内的最小值。

　　思路:我们需要一个二维数组来存储信息,存储方式是dp[i][j]

其中i代表查询的左端点,j为查询范围是i+2^j范围内的最小值,数列本身定为a[i]

我们首先确定dp[i][0]一定就是a[i]本身,这是显然的,然后我们需要找出dp转移方程

那方程是什么呢？

　　首先我们确定区间为给出的l,r,区间范围就是r-l+1,我们可以将区间

一分为二,然后分别找到左边和右边的最小值,取两值的min值便是区间所求

那我们可以得出结论:dp[i][j]=min(dp[i][j-1],dp[i+(1<<j-1)][j-1])

解释一下,dp[i][j]为从i开始2^j为范围中的最小值,即为我们所求dp[i][j-1]

从i开始2^(j-1)范围内的最小值,是所求范围的前一半

dp[i+(1<<j-1)][j-1] ,从i开始2^(j-1)范围内的最小值,是所求范围的后一半

　　然后我们还需要注意一点,就是在预处理dp数组时我们需要将i放在里层

j放在外层,因为我们是以i为开始点进行dp的,在长度为2^j时我们需要把每一个

可出发的i都处理好,所以要将j放在外层

　　最后就是区间查询了,我们需要一个值为log2(r-l+1),代表我们的j,这个式子

就是我们还原区间的方式,我们j代表的是2^j,那自然还原就是log2回去了

　　代码:

 #include <bits/stdc++.h>

 using namespace std;

 int n,m,x,y,k;

 long long a[];

 long long dis[][];

 inline void rmq(){

     for(register int i=;i<=n;i++) dis[i][]=a[i];

     for(register int j=;(<<j)<=n;j++)

     for(register int i=;i+(<<j)-<=n;i++)//将i放在里层因为咱们要先更新每一个i的位置关系

     dis[i][j]=min(dis[i][j-],dis[i+(<<j-)][j-]);

     return;

 }

 inline void search(int l,int r){

     k=log2(r-l+);

     printf("%lld\n",min(dis[l][k],dis[r-(<<k)+][k]));

     return;

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(register int i=;i<=n;i++) scanf("%lld",&a[i]);

     rmq();//预处理

     for(register int i=;i<=m;i++){

         scanf("%d%d",&x,&y);

         search(x,y);

     }

     return ;

 }

RMQ

　　end;

巴特西

数据结构——RMQ

最新文章

热门文章