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));

}