数据结构--ST表

ST表

https://www.cnblogs.com/qq965921539/p/9608980.html
与线段树相比，预处理复杂度同为O(nlogn),查询时间上，ST表为O(1),线段树为O(nlogn)

int a[maxn],st[maxn][20];

void rmq(int n)            //建立st表
{
    for(int j = 1; (1<<j) <= n; j++)
        for(int i = 1; i+(1<<j)-1 <= n; i++)
            st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}

int ask(int l,int r)        //询问l,r区间
{
    int k = log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}

数据结构--ST表

原文：https://www.cnblogs.com/hezongdnf/p/12239617.html