hihocoder第16周（RMQ-ST算法）

题目链接：

huangjing

思路：新学会的一种算法，RMQ（Rangle Minimum Query）从名字来看，觉得就是查询最小值的，哈哈，

大白上有仔细的讲解。dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1])，具体的图请看大白，真是神奇的方法。。

预处理的复杂度为O(N*logN),查询就是O(1)的复杂度。

方法二：线段树解法  复杂度为O(Q*logN).

题目：

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

const int maxn=1000000+10;


int a[maxn],dp[maxn][20],n,q,ans[maxn];

void RMQ_init()
{
    for(int i=1;i<=n;i++)  dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<(j-1))-1<=n;i++)
           dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}

int RMQ_Query(int l,int r)
{
    int k=0;
    while(1<<(k+1)<=r-l+1)  k++;
    return min(dp[l][k],dp[r-(1<<k)+1][k]);
}

int main()
{
    int l,r,k;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        RMQ_init();
        scanf("%d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d%d",&l,&r);
            ans[i]=RMQ_Query(l,r);
        }
        for(int i=1;i<=q;i++)
          printf("%d\n",ans[i]);
    }
    return 0;
}

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=1000000+10;

int tree[maxn<<2],n,q,ans[maxn];

void push_up(int dex)
{
    tree[dex]=min(tree[dex<<1],tree[dex<<1|1]);
}

void buildtree(int dex,int l,int r)
{
    if(l==r)
    {
        scanf("%d",&tree[dex]);
        return;
    }
    int mid=(l+r)>>1;
    buildtree(dex<<1,l,mid);
    buildtree(dex<<1|1,mid+1,r);
    push_up(dex);
}

int Query(int dex,int L,int R,int l,int r)
{
    if(l<=L&&r>=R)
        return tree[dex];
    int mid=(L+R)>>1;
    if(l>mid)  return Query(dex<<1|1,mid+1,R,l,r);
    else if(r<=mid)  return Query(dex<<1,L,mid,l,r);
    else return min(Query(dex<<1,L,mid,l,r),Query(dex<<1|1,mid+1,R,l,r));
}

int main()
{
    int l,r;
    while(~scanf("%d",&n))
    {
         buildtree(1,1,n);
         scanf("%d",&q);
         for(int i=1;i<=q;i++)
         {
            scanf("%d%d",&l,&r);
            ans[i]=Query(1,1,n,l,r);
         }
        for(int i=1;i<=q;i++)
            printf("%d\n",ans[i]);
    }
    return 0;
}