RMQコード

RMQは,区間最値クエリであり,長さnの数列Aに対して,若干の質問RMQ(A,i,j)(i,j<=n)を回答し,数列Aの中でi,jに下付きの最小(大)値を返す.
主な方法:

は素朴(すなわち探索)であり、複雑度はO(n)

である.

セグメントツリーは、複雑度が低く、適用範囲も広いが、実現複雑度が高い.

STアルゴリズムは、最大値を求める例として、d[i,j]が[i,i+2^j−1]という区間内の最大値を表すとすると、[a,b]区間の最大値を尋ねるとmax(d[a,k],d[b−2^k+1,k])となり、kは2^k<=b−a+1(すなわち長さ)を満たす最大k、すなわちk=[ln(b−a+1)/ln(2)]となる.

以下にSTアルゴリズム実装最小値クエリを示す.

#include<iostream>
#include<cmath>
using namespace std;

#define M 100010
#define MAXN 500
#define MAXM 500
int dp[M][18];
/*
*  RMQ ST  
*  RMQ   makermq(int n,int b[]) O(nlog(n))      
*dp[i][j]    i i+2^j -1       ( i    2^j  )
*dp[i][j]=min{dp[i][j-1],dp[i+2^(j-1)][j-1]}
*  RMQ rmq(int s,int v)
* s-v     2^k   
*s         
*v         
*  k=(int)log2(s-v+1)
*        min(dp[s][k],dp[v-2^k+1][k])
*/

int min(int a, int b) {
	if (a>b)
		return b;
	return a;
}
void makermq(int n,int b[])
{
    int i,j;
    for(i=0;i<n;i++)
        dp[i][0]=b[i];
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
int rmq(int s,int v)
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return min(dp[s][k],dp[v-(1<<k)+1][k]);
}

void makeRmqIndex(int n,int b[]) //          
{
    int i,j;
    for(i=0;i<n;i++)
        dp[i][0]=i;
    for(j=1;(1<<j)<=n;j++)
        for(i=0;i+(1<<j)-1<n;i++)
            dp[i][j]=b[dp[i][j-1]] < b[dp[i+(1<<(j-1))][j-1]]? dp[i][j-1]:dp[i+(1<<(j-1))][j-1];
}
int rmqIndex(int s,int v,int b[])
{
    int k=(int)(log((v-s+1)*1.0)/log(2.0));
    return b[dp[s][k]]<b[dp[v-(1<<k)+1][k]]? dp[s][k]:dp[v-(1<<k)+1][k];
}

int main()
{
    int a[]={3,4,5,7,8,9,0,3,4,5};
    //    
    makeRmqIndex(sizeof(a)/sizeof(a[0]),a);
    cout<<rmqIndex(0,9,a)<<endl;
    cout<<rmqIndex(4,9,a)<<endl;
    //     
    makermq(sizeof(a)/sizeof(a[0]),a);
    cout<<rmq(0,9)<<endl;
    cout<<rmq(4,9)<<endl;
    return 0;
}