浅谈RMQ算法

朱雀 2021-12-05 05:09 404阅读 0赞

定义  
RMQ (Range Minimum/Maximum Query)问题：是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。

ST函数：  
有的同学说，很简单，两个for循环遍历就行了，这是最简单的方法，要是给你的数据范围N=500000 1s 你咋办 O（n \* n）。TLE…

接下来就给大家介绍一种RMQ方法。  
预处理O(n\*logn) 查询O（1）

一个数组arr： 1 6 2 8 9 3 7  
我们用一个二维数组dp\[ i \]\[ j \]表示从i开始连续的2的j次方个数中的最值  
dp\[2\]\[2\]表示从第二个数6开始连续的4个数（2的平方）中的最大值（假设求最大值）  
6 2 8 9 这四个数中，也就是dp\[2\]\[2\]=9 是不是很容易理解。

普遍情况：  
dp\[i\]\[j\]是从 i 开始连续的2的 j 次方中的最值，我们把这个区间分成相等的两部分  
前一部分为 i ~ 2的（j-1）次方 -1 表示为dp\[i\]\[j-1\]  
后一部分为 i + 2的（j-1）次方 ~ 2的 j 次方-1 表示为dp\[ i+( 1<<(j-1) ) \]\[j-1\]

转移方程为 dp\[i\]\[j\]=max(dp\[i\]\[j-1\],dp\[i+(1<<(j-1))\]\[j-1\])

void st_prework()
    {
     	for(int i=1;i<=n;i++) 
     	{
      		dp[i][0]=num[i];
    	 }
     	int N=log(n)/log(2)+1;
     	for(int j=1;j<N;j++)
     	{
      		for(int i=1;i+(1<<j)-1<=n;i++)
      		{
       			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
      		}
     	}
    }

很多同学就直接把这个板子给背过了，其实这样没用，你要理解每个for循环变量在递推式的意义，问你一个问题，为什么是外循环是j，内循环是i ，相信很多刚入门的同学答不上来吧，大佬略过。

解释：我们在递推的时候，  
先比较自己，  
在比较相邻的两个数，遍历一边数组，  
在比较相邻的四个数，遍历一遍数组，  
八个…  
十六个…  
…

所以2的指数幂先不动，i从1遍历到n-（1<<j） +1 比较相邻的2的指数幂的大小。

再看O（1）的查找

ll st_query(ll l,ll r)
    {
     	ll len=log(r-l+1)/log(2);
     	return max(dp[l][len],dp[r-(1<<len)+1][len]);
    }

我们先计算\[l.r\] 中的2的指数幂是多少，看看我们最大能遍历到哪。log是向下取整  
看两个区间就行了，dp\[l\]\[len\] 表示从l连续的2的len次方区间中的最大值，  
dp\[r-(1<<len)+1\]\[len\] 表示剩下的一段区间，两个区间在预处理时的最大值已经求出来，所以二者取个最大的就行了。所以查询效率为O（1）。

给两个例题：  
[洛谷 P3865 （模板题）][P3865]

简单模板题:不解释

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    int a[maxn],dp[maxn][100];
    int n,m;
    int read()
    {
        int num = 0;
        char c = getchar();
        while(c > '9' || c < '0')c = getchar();
        while(c >= '0'&& c<= '9')
        {
            num=num*10+c-'0';
            c = getchar();
        }
        return num;
    }
    void write(int x)
    {
    	if(x<0)
    	{
    		putchar('-');
    		x=-x;
    	}
    	if(x>9)	
    		write(x/10);
    	putchar(x%10+'0');
    }
    void st_prework()
    {
    	for(int i=1;i<=n;i++)
    	{
    		dp[i][0]=a[i];
    	}
    	ll t=log(n)/log(2)+1;
    	for(int j = 1 ; j < t ; j++)
    	{
    		for(int i=1;i<=n-(1<<j)+1;i++)
    			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    	} 
    }
    int st_query(int l,int  r)
    {
    	int k=log(r-l+1)/log(2);
    	return max(dp[l][k],dp[r-(1<<k)+1][k]);	
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	n=read(),m=read();
    	for(int i=1;i<=n;i++)
    		a[i]=read();
    	st_prework();
    	for(int i=1;i<=m;i++)
    	{
    		int l,r;
    		l=read(),r=read();
    		int k=st_query(l,r);
    		printf("%d\n",k);
    	
    	}
    	return 0;
    }

第二题  
[Frequent values][]

这题我们求的区间大值不是区间的每个数的最大值，而是出现次数（本题中用num数组）的最大值。  
用num表示这个元素出现的次数  
用rt表示这个元素最后出现的位置，等下解释。  
\-1 -1 1 1 1 1 3 10 10 10  
num 1 2 1 2 3 4 1 1 2 3  
rt 2 2 6 6 6 6 7 10 10 10

分3种情况  
1.  
如果这个区间正好所有元素相同即a\[l\]==a\[r\]  
ans=r-l+1  
2.  
如果取得区间把一段连续的数在左端点切断 比如例子中取【5，10】 第5个元素是1，第4个元素也是1，这时候就需要计算一下，是被切断的数频率大，还是这些元素后面的数出现的频率大。  
这是rt数组就用到了，让t取一个rt【l】和r的最小值，t代表被切断的数的最后一个的位置，只需要计算max（t-l+1，st\_query(t+1,r) ）右端点的数被切断没关系，因为num存的数是从小到大存的，切断了就是这个数的最多出现的次数。  
3.  
区间没有切断，区间也不是所有数都相同，所以求st\_query(l,r)就行了。

#include<iostream>
    #include<cstring>
    #include<cmath>
    #include<cstdio>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    ll a[maxn],rt[maxn],num[maxn],dp[maxn][20];
    ll n,k;
    void st_prework()
    {
    	for(int i=1;i<=n;i++) 
    	{
    		dp[i][0]=num[i];
    	}
    	int N=log(n)/log(2)+1;
    	for(int j=1;j<N;j++)
    	{
    		for(int i=1;i+(1<<j)-1<=n;i++)
    		{
    			dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
    		}
    	}
    }
    ll st_query(ll l,ll r)
    {
    	ll len=log(r-l+1)/log(2);
    	return max(dp[l][len],dp[r-(1<<len)+1][len]);
    }
    int main()
    {
    	while(~scanf("%lld",&n))
    	{
    		if(n==0)	break;
    		scanf("%lld",&k);
    		memset(a,0,sizeof(a));
    		memset(rt,0,sizeof(rt));
    		for(int i=1;i<=n;i++)
    		{
    			scanf("%lld",&a[i]);
    			num[i]=1;
    		}
    		a[0]=9999999;
    		for(int i=1;i<=n;i++)
    		{
    			if(a[i-1]==a[i])
    			num[i]=num[i-1]+1;
    		}
    
    		for(int i=n;i>0;i--)
    		{
    			if(a[i]==a[i+1])
    				rt[i]=rt[i+1];
    			else
    				rt[i]=i;
    		}
    		
    		st_prework();
    		for(int i=1;i<=k;i++)
    		{
    			ll l,r,ans;
    			scanf("%lld%lld",&l,&r);
    			if(a[l]==a[r])
    				ans=r-l+1;
    			else
    			{
    				if(a[l-1]==a[l])   //数被截断
    				{
    					ll t=min(rt[l],r);
    					ans=max(t-l+1,st_query(t+1,r));
    				}
    				else
    					ans=st_query(l,r);
    			}
    			printf("%lld\n",ans);
    		}
    	}
    	return 0;
    }

[P3865]: https://www.luogu.org/problemnew/show/P3865
[Frequent values]: http://poj.org/problem?id=3368