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;
}