代码：

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 100005
int n, m;
int a[maxn];
int f[maxn][35], lg[35];

int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') { f = (ch == '-' ? -1 : f); ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

void ST_prework() {
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
    int t = lg[n] + 1;
    for (int j = 1; j < t; j++)
        for (int i = 1; i <= n - (1 << j) + 1; i++) f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

int ST_query(int l, int r) {
    int k = lg[r - l + 1];
    return max(f[l][k], f[r - (1 << k) + 1][k]);
}

signed main() {
    for (int i = 1; i <= n; i++)  lg[i] = lg[i >> 1] + 1;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ST_prework();
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << ST_query(l, r) << endl;
    }
    return 0;
}

另外，为什么 ST_prework() 函数中，二重循环的顺序是 j 在前，i 在后？