「知识总结」RMQ 问题 - Sparse Table 表【RMQ】

简介

ST\text {ST} 表是解决 RMQ\text {RMQ} 问题的一个常用方法。

方法

  • 定义: 记 aia_i 为原数组,dp(i,j)dp(i, j) 表示区间 [i,i+2j1][i, i+2^j-1] 的最大 (小) 值。
  • 初始化: 区间 [i,i][i, i] 的答案为 aia_i,即 dp(i,0)=aidp(i, 0)=a_i
  • 转移: 将区间分为两部分,dp(i,j)=max(dp(i,j1), dp(i+2j1,j1))dp(i, j) = \max(dp(i, j-1), \ dp(i+2^{j-1}, j-1))
  • 答案: 对于询问 [l,r][l,r],令 k=floor(log2(rl+1))k = floor(log_2(r-l+1)),则答案为 max(dp(l,k), dp(r2k+1,k))\max(dp(l, k), \ dp(r-2^k+1, k))
  • 复杂度: 预处理为 O(nlogn)O(n \log n),单次查询为 O(1)O(1),总复杂度 O(nlogn+m)O(n \log n + m)

实现

(Luogu - 3865)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 10;
int n, m, dp[maxn][22];

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &dp[i][0]);
}
for (int i = 1; i <= 20; 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;
scanf("%d %d", &l, &r);
int k = log(r - l + 1) / log(2);
printf("%d\n", max(dp[l][k], dp[r - (1 << k) + 1][k]));
}
return 0;
}