ST表(RMQ问题)

ST表能够O(1)地解决区间[l,r]之间最值问题

1.建表，首先明白ST[i][j]，表示的是区间[i, i+(1<

void init（）{
    
    for(int i=1; i<=n; i++){
        ST[i][0]=a[i];
    }
}

因为ST[i][0]表示区间[i,i+(1<<0)-1]，也就是[i,i],即a[i]本身。

然后建表，首先确定k=log2(区间大小),这么做的目的是确定最大的j以保证ST[i][i+(1<

void build(int l, int r){
    int k = log2(r-l+1);
    init();
    for(int j=1; j<=k; j++)
        for(int i=1; i<=r-(1<1; i++){
            ST[i][j] = max(ST[i][j-1], ST[i+(1<<(j-1))][j-1]);//[i,i+(1<
        }
}

可以通过下面的例子进一步理解：

下列有10个数，从序列1开始到10；第2行到第11行是ST存储的情况：注意行为j表示当前区间大小，列为i表示区间起始序号。便于理解现在改为i为行，列为j。

2.查询给定区间[l,r]的最值：

跟建表一样确定 k = log2(r-l+1), 然后从ST[l][k]和ST[r-(1<

int find(int l, int r){
    int k = log2(r-l+1);
    return max(ST[l][k], ST[r-(1<1][k]); 
}