st 表算法模板

左手的ㄟ右手 2022-05-15 12:23 167阅读 0赞

借鉴于：[https://blog.csdn.net/Hanks\_o/article/details/77547380][https_blog.csdn.net_Hanks_o_article_details_77547380]  
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)\]。

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

有个公式，就是2^log(len)>len/2;而len=r-l+1; len为区间查询长度

查询l到r的区间最值，min(从l往后2^t的最小值，从r往前2^t的最小值)  
t=log\[len\],  
而前多半部分就是st\[t\]\[l\],  
设m+2^len-1=r;m为开始下标  
所以 m=r-2^len+1;  
后半部分：st\[t\]\[r-2^len+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));
    
    }

[https_blog.csdn.net_Hanks_o_article_details_77547380]: https://blog.csdn.net/Hanks_o/article/details/77547380