首页 > 代码库 > RMQ算法

RMQ算法

2024-09-23 05:26:40   216人阅读

一.概述

RMQ（Range Minimum/Maximum Query），即区间最值查询，是指这样一个问题：对于长度为n的数列A，回答若干询问RMQ（A,i,j）(i,j<=n)，返回数列A中下标在i，j之间的最小/大值。这两个问题是在实际应用中经常遇到的问题，下面介绍一下解决这两种问题的比较高效的算法。当然，该问题也可以用线段树（也叫区间树）解决，算法复杂度为：O(N)~O(logN)，这里我们暂不介绍

二.算法思路

1.首先利用dp预处理出从i点开始往后的2^j的最大值,dp的时候将其拆分成两段

2.查询出左端点以i开始，终点以j开始的最大值

 

一篇非常好的博客http://blog.csdn.net/liang5630/article/details/7917702

 

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 int a[2000001]; 7 int minn[2000001][15]; 8 int fastpow(int a,int p) 9 {10     int base=a;11     int ans=1;12     while(p)13     {14         if(p%2)ans*=base;15         base*=base;16         p/=2;17     }18     return ans;19 }20 int main()21 {22     int n,m;23     scanf("%d%d",&n,&m);24     for(int i=0;i<=n;i++)25         for(int j=0;j<=14;j++)26         minn[i][j]=0x7ff;27     for(int i=1;i<=n;i++)28         scanf("%d",&minn[i][0]);// 第i个点跳1步能到达的点是其本身 29     for(int j=0;j<=14;j++)// 2^j 30     {31         for(int i=1;i<=n;i++)// 根据dp的无后效性，要在j一定的情况下把每一个点跳完之后能到达的位置处理出来 32         {33             if(i+(1<<j)-1<=n)// 第二段区间保证在范围之内 34             minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j]);35         }36     }37     // 三段区间 i——i+2^(j-1)-1——i+2^j-1 38     printf("0\n");39     int k=log(m)/log(2);// 保证求值区间的长度在要求的范围之内 40     // 带求区间 i-m to i41     for(int i=2;i<=n;i++)42     {43         printf("%d\n",min(minn[i-m][k],minn[i-fastpow(2,k)+1][k]));44         //                左端点            右端点 45     }46     return 0;47 }

 

RMQ算法


联系
我们