ST 表

ST 表

ST 表运用了倍增的思想。

其中 $dp_{i, j} = \max(i \to i + 2^j - 1)$，也就是 $dp_{i, j}$ 的值是区间 $[i, i + 2^j - 1]$ 中的最大值。

通过上面的定义，显然 $dp_{i,0} = \max(i \to i + 2^0 - 1) = \max(i \to i) = a_i$。

我们可以得出递推式：$dp_{i, j} = max([i, i + 2^{j - 1} - 1], [i + 2^{j - 1}, i + 2^j - 1]) = max(dp_{i, j - 1}, dp_{i + 2^{j - 1}, j - 1})$。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
int n, m, a[1000005], dp[100005][25];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        dp[i][0] = a[i];
    } 
    for (int i = 1; i <= 21; i ++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j ++) {
            dp[j][i] = max(dp[j][i - 1], dp[j + (1 << (i - 1))][i - 1]);
        }
    }
    while (m --) {
        int l, r; cin >> l >> r;
        int c = __lg(r - l + 1);
        cout << max(dp[l][c], dp[r - (1 << c) + 1][c]) << "\n";
    }
    return 0;
}