ST 表

luckydrawbox · 2021-08-29 12:08:47 · 个人记录

使用前要确定操作运算，要保证这是一个可重复贡献的运算，如 \max,\min,\gcd 等。

int op(int x,int y){
    return max(x,y);
}

把上面的 \max 改成其他运算就可以了。

使用前要初始化，init(n,a)：初始化 a_{1\sim n}。

ask(l,r) 可以查询 [l,r] 的值。

struct ST{
    int f[N][32];
    int Log2[N];
    int op(int x,int y){
        return max(x,y);
    }
    void init(int n,int *a){
        memset(f,0,sizeof(f));
        for(int i=1,j=0;i<=n;i++){
            f[i][0]=a[i];
            Log2[i]=j;
            if(i+1==1<<(j+1))
                j++;
        }
        int t=Log2[n]+1;
        for(int j=1;j<t;j++)
            for(int i=1;i<=n-(1<<j)+1;i++)
                f[i][j]=op(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    }
    int ask(int l,int r){
        int k=Log2[r-l+1];
        return op(f[l][k],f[r-(1<<k)+1][k]);
    }
}st;

时间复杂度 O(n\log n)，空间复杂度 O(n\log n)。