\(O(nlog(n))\) 预处理，\(O(1)\) 查询区间最大值/可重复计算的区间值。

template <typename T>
struct ST {
    std::vector<std::vector<T>> max;
    std::vector<int> lg;
    std::function<T(const T &, const T &)> merge;

    ST(std::vector<T> &vec, std::function<T(const T &, const T &)> merge = [](const T &a, const T &b) { return std::max(a, b); }) : lg(vec.size()), merge(merge) {
        int len = vec.size() - 1;
        lg[1] = 0;
        for (int i = 2; i <= len; i++) {
            lg[i] = lg[i >> 1] + 1;
        }
        int lenofmax = 0;
        for (int i = 0; i <= 30; i++) {
            if (len & (1 << i))
                lenofmax = i;
        }
        max = std::vector<std::vector<T>>(lenofmax + 1, std::vector<T>(vec.size()));
        max[0] = vec;
        for (int i = 1; i <= lenofmax; i++) {
            for (int j = 1; j + (1 << (i - 1)) <= len; j++) {
                max[i][j] = merge(max[i - 1][j], max[i - 1][j + (1 << (i - 1))]);
            }
        }
    }

    T query(int l, int r) {
        int p = lg[r - l];
        return merge(max[p][l], max[p][r - (1 << p) + 1]);
    }
};

test: P3865 【模板】ST 表 && RMQ 问题