综合：ST 表区间最大

运行下面这段程序：

综合：前缀和 / 树状数组 / 线段树 / ST 表，按题目要求选对结构。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<vector<int>> st_build(const vector<int>& a) {
    // ST 表（区间最大值）：st[j][i] 是 a[i .. i + 2^j - 1] 的最大值
    int n = (int)a.size();
    vector<vector<int>> st;
    st.push_back(a);
    for (int j = 1; (1 << j) <= n; j++) {
        vector<int> cur;
        for (int i = 0; i + (1 << j) <= n; i++) {
            cur.push_back(max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]));
        }
        st.push_back(cur);
    }
    return st;
}

int st_query(const vector<vector<int>>& st, int l, int r) {
    // O(1) 求 a[l..r]（闭区间）的最大值：j 是区间长度以 2 为底的对数（向下取整）
    int j = 0;
    while ((1 << (j + 1)) <= r - l + 1) j++;
    return max(st[j][l], st[j][r - (1 << j) + 1]);
}

int main() {
    cout << st_query(st_build({5, 3, 8, 1, 9, 2}), 0, 5) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）