关于st表的推导

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+7;
int st[maxn][32];
int a[maxn],n;
void init(){
    int i,j;
    //st[i][j]表示i到i+2^j-1区间的最小值
    //先预处理区间长度为1的
    for(i=0;i<n;++i)  st[i][0]=a[i];
    for(i=0;i<n;++i){
        for(j=1;i+2^(j)-1<n;++j){
            //i~i+2^(j-1)-1
            //i+2^(j-1)~i+2^(j-1)+2^(j-1)-1=>i+2^j-1;
            //一定要发现这个显然的事实就是
            //2^(j-1)+2^(j-1)=2^j; 
            st[i][j]=min(s[i][j-1],s[i+2^(j-1)][j-1]);
        }
    }
}
int queryMin(int l,int r){
    int len=r-1+1;
    int index=log(len);
    //st[l][index] l~l+2^(index)-1
    //2^(index)<=(r-l+1); l+2^(index)-1<=r
    //r-(l+2^(index)-1)>=0 还差多少元素没放进来
    //x+LEN=l+2^(index)-1+(r-(l+2^(index)-1));
    //x+2^(index)-1=r;//区间长度固定。。起点是多少才能正好跑到r,列一个简单的方程才能解决 
    //x=r+1-(2^(index));
    return min(st[l][index],st[r+1-(2^(index))][index]);
}
int main(){
    while(~scanf("%d",&n)){
        int i,q,l,r;
        for(i=0;i<n;++i){
            scanf("%d",a+i);
        }
        init();
        scanf("%d",&q);
        for(i=0;i<q;++i){
            scanf("%d%d",&l,&r);
            printf("%d\n",query(l,r));
        }
    }
    return 0;
}

上面这个^符号代表幂次。。而c++里只有异或。。这就是为什么这是一个伪代码的意思

先来一个终极伪代码

推导过程如上。。

下面给一个真正的的代码

#include <bits/stdc++.h>

using namespace std;
const int maxn=1e6+7;
int st[maxn][32];
int a[maxn],n;
void init(){
    int i,j;
    //st[i][j]表示i到i+2^j-1区间的最小值
    //先预处理区间长度为1的
    for(i=0;i<n;++i)  st[i][0]=a[i];
    for(i=0;i<n;++i){
        for(j=1;i+(1<<j)-1<n;++j){//这里有一个优化。。本来是小于32的。。问题规模较小是只是相当于一个常数的优化 
            //i~i+2^(j-1)-1
            //i+2^(j-1)~i+2^(j-1)+2^(j-1)-1=>i+2^j-1;
            //一定要发现这个显然的事实就是
            //2^(j-1)+2^(j-1)=2^j; 
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
        }
    }
}
int queryMin(int l,int r){
    int k=log(r-l+1);
    //st[l][index] l~l+2^(index)-1
    //2^(index)<=(r-l+1); l+2^(index)-1<=r
    //r-(l+2^(index)-1)>=0 还差多少元素没放进来
    //x+LEN=l+2^(index)-1+(r-(l+2^(index)-1));
    //x+2^(index)-1=r;//区间长度固定。。起点是多少才能正好跑到r,列一个简单的方程才能解决 
    //x=r+1-(2^(index));
    return min(st[l][k],st[r+1-(1<<k)][k]);
}
int main(){
    while(~scanf("%d",&n)){
        int i,q,l,r;
        for(i=0;i<n;++i){
            scanf("%d",a+i);
        }
        init();
        scanf("%d",&q);
        for(i=0;i<q;++i){
            scanf("%d%d",&l,&r);
            printf("%d\n",queryMin(l-1,r-1));
        }
    }
    return 0;
}

还有一个对于新手来说理解的坑。。那就是int x=log(val)实际上是对log的值向下取整。。这一点非常重要

只有这个成立我们注释里的推导才会成立。。另外有一些没用的推导。。但是我没有删掉。。这是因为想记录一下我全部的思考过程
原文链接: https://www.cnblogs.com/linkzijun/p/6347769.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍