C++ – ST 表

lli n;
lli arr[maxn];
lli lg[maxn];
lli st[maxn][32];

inline lli flg(lli x) {
    if (lg[x]) return lg[x];
    lli tmp = x;
    lli res = 0;
    while (tmp) tmp >>= 1, ++res;
    return lg[x] = res - 1;
}

inline void init_st() {
    for (lli i = 1; i <= n; ++i)
        st[i][0] = arr[i];
    for (lli i = 1; 1 << i <= n; ++i)
        for (lli j = 1; j + (1 << i) - 1 <= n; ++j)
            st[j][i] = max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
}

inline lli ask_st(lli l, lli r) {
    if (l > r) return -1;
    lli k = flg(r - l + 1);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}