原理

ST表：又名稀疏表，预处理 NlogN，单次查询 1，时间复杂度：O(NlogN + M)
ST[p][i] 代表从 i 点开始共 2 ^ p 个数的最大值，即 [i, i + 2 ^ p - 1] 区间的最大值

实现

void ST(){
        for(int i = 1; i <= n; i ++) st[0][i] = x[i];
        int p = log(n) / log(2);
        for(int k = 1; k <= p; k ++){
            for(int i = 1; i + (1 << k) - 1 <= n; i ++){
                st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
            }
        }
    }
int query(int l, int r){
        int p = __lg(r -  l + 1);
        // int p = log(r - l + 1) / log(2);
        return max(st[p][l], st[p][r - (1 << p) + 1]);
}