RMQ倍增板子（区间最值查询问题）（静态）

找某个区间内的最大最小值；

思想：动态规划

用f【i】【j】表示以第i个数为起点，往后连续2^j个数中的最大值；

log数组向下取整；

code：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int f[maxn][25],a[maxn],Log[maxn];
int n,m;

void RMQ()
{
    int i,j;
    for(i=1;i<=n;++i)
      f[i][0]=a[i];
    for(j=1;(1<<j)<=n;++j)
      for(i=1;i+(1<<(j-1))<=n;++i)
        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
void GetLog()
{
    int i;
    Log[1]=0;
    for(i=2;i<=n+1;++i)
      Log[i]=Log[i/2]+1;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    GetLog();
    RMQ();
    while(m--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int k=Log[y-x+1];
        printf("%d
",max(f[x][k],f[y-(1<<k)+1][k]));
    }

    //system("pause");
    return 0;
}

 线段树查询区间最大值；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
int n,m,a[maxn];
struct node{
    int l,r;
    int ma,sum;
}tree[maxn*4+10];
struct seg_tree{
    void push_up(int x)
    {
        tree[x].ma=max(tree[x<<1].ma,tree[x<<1|1].ma);
    }
    void build(int x,int l,int r)
    {
        tree[x].l=l,tree[x].r=r;
        tree[x].ma=0;
        if(l==r)
         {
             tree[x].ma=a[l];
             return ;
         }
         int mid=(l+r)>>1;
         build(x<<1,l,mid);
         build(x<<1|1,mid+1,r);
         push_up(x);
    }
    int quary(int x,int l,int r)
    {
        int L=tree[x].l,R=tree[x].r;
        if(l<=L&&R<=r)
          return tree[x].ma;
        int ans=0;
        int mid=(L+R)>>1;
        if(mid>=l) ans=max(ans,quary(x<<1,l,r));
        if(mid<r) ans=max(ans,quary(x<<1|1,l,r));
        return ans;
    }

}st;
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++) cin>>a[i];
    st.build(1,1,n);
    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<st.quary(1,l,r)<<endl;
    }
    system("pause");
    return 0;
}