st 表算法模板

st表是基于二分的思想，

st[i][j]表示j到j+2^n-1区间内的最值，（长度为2^n），

构建的时候用二分构建，那么st[i][j]如何用其他状态来继承呢？

j到j+2^i-1的长度为2^i，那么一半的长度就等于2^(i-1)。

那么前半段的状态表示为st[i-1][j]。

后半段的长度也为2^(i-1)，起始位置为j+2^(i-1)。 那么后半段的状态表示为st[i-1][j+2^(i-1)]。

所以： st[i][j]=min(st[i-1][j],st[i-1][j+2^(i-1)]。

那么预处理部分结束了，看看查询部分

int t=log[r-l+1];
printf("%d\n",min(st[t][l],st[t][r-2^t+1]));      

//st表，区间最值问题，预处理nlogn,查询 1，不支持在线修改，
//线段树，预处理nlogn，查询logn,支持在线修改 

#include<iostream>
#include<cstdio>

using namespace std;
int n;
const int N=1000;
int log[N];
int stmin[N][N],stmax[N][N];
int a[N];
int bin[N]; 
void init(){
    log[0]=-1;
    bin[0]=1;
    for(int i=1;i<=n;i++){
        bin[i]=bin[i-1]*2;
    }
    for(int i=1;i<=n;i++){
        log[i]=log[i/2]+1;

    }
    for(int i=1;i<=n;i++){
        stmin[0][i]=a[i];
        stmax[0][i]=a[i];

    }
    for(int i=1;i<=log[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            stmin[i][j]=min(stmin[i-1][j],stmin[i-1][j+(1<<(i-1))]);
            stmax[i][j]=max(stmax[i-1][j],stmax[i-1][j+(1<<(i-1))]);
        }
    }

}
int rmq_max(int l,int r){
    int t=log[r-l+1];//2^log(len)>len/2
    return max(stmax[t][l],stmax[t][r-(1<<t)+1]);
}
int rmq_min(int l,int r){
    int t=log[r-l+1];
    return min(stmin[t][l],stmin[t][r-(1<<t)+1]);
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    init();
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%d\n",rmq_min(x,y));

}