ST表

template<class T>
struct SparseTable {
    vector<vector<T>> st;
    vector<int> lg;
    // 传入的 vector 的下标必须以 1 为基础
    SparseTable(const vector<T> &s) {
        const int n = s.size() - 1;
        st.assign(n + 1, vector<T>(22, 0));
        lg.resize(n + 1);
        for (int i = 2 ; i <= n ; i++) {
            lg[i] = lg[i >> 1] + 1;
        }
        for (int i = 1 ; i <= n ; ++i) {
            st[i][0] = s[i];
        }
        for (int j = 1 ; j <= lg[n] ; j++) {
            for (int i = 1 ; i + (1 << j) - 1 <= n ; i++) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    T query(int L, int R) {
        int k = lg[R - L + 1];
        return max(st[L][k], st[R - (1 << k) + 1][k]);
    }
}; // SparseTable