ST表裸题

什么是ST表

ST表(又称稀疏表，Sparse Table)，是专门解决RMQ问题的一种数据结构。
它采用倍增思想，可以 $O(nlogn)$ 预处理， $O(1)$ 查询区间最值。

思想

max(a, b, c) = max(max(a, b), max(b, c))
即两个较小的、有重叠的区间的最值直接推出一个大区间最值。

记 maxn[x][i] 表示第 $x$ 个数开始，长度为 $2^i$ 的一段数的最值，那么 maxn[x][i] = max(maxn[x][i - 1], maxn[x + 2 ^ (i - 1)][i - 1])
这样，以每个点为起点都有 $logn$ 个区间，每个区间可以 $O(1)$ 求出，则预处理总时间、空间复杂度都为 $O(nlogn)$。

注意预处理出每个数的以2为底的对数。

代码

int main(){
    int a[MAXN], lg[MAXN] = {-1}, maxn[MAXN][50];
    int n, m, l, r;

    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
        lg[i] = lg[i >> 1] + 1;  //预处理以2为底的对数
    }

    for(int i = 1; i <= n; i++)
        maxn[i][0] = a[i];

    for(int i = 1; i <= lg[n]; i++)
        for(int j = 1; j + (1 << i) - 1 <= n; j++)
            maxn[j][i] = max(maxn[j][i - 1], maxn[j + (1 << (i - 1))][i - 1]);  //dp思想

    while(m--){
        scanf("%d%d", &l, &r);
        int len = lg[r - l + 1];
        printf("%d\n", max(maxn[l][len], maxn[r - (1 << len) + 1][len]));
    }
    return 0;
}