发布于 ,更新于 

RMQ/ST表

目标是解决 RMQ 问题,即对于一个大区间,短时间内查询一个小区间的最大最小值

下文以最大值为例说明

ST 表本质上是一个动态规划(倍增的)

先利用倍增(二进制拆分)预处理然后 \(\operatorname{O}(1)\) 查询,比线段树快,但是只支持静态区间

原理

预处理

\(f_{i,j}\) 表示从 \(i\) 开始,长度为 \(2^j\) 的区间中的最大值

预处理阶段,对于 \(f_{i,j}\) 来说,直接 \[ \max\{ f_{i,{j-1}},f_{i+2^{j-1},j-1} \} \] 递推即可,非常容易想,时间复杂度为 \(\operatorname{O}(n\log n)\)

查询

对于一个区间 \([L,R]\) 来说,假设他的长度为 \(len\)

很容易能找到一个 \(k\) 使得 \[ \frac{len}{2} < 2^k \leqslant len \]

显然 \([L,R]\)\([L,2^k],[R-2^k-1,k]\) 严格包含,因此 ST 表中查询最大最小值的时间复杂度是常数级别的,而不是线段树的 \(\log\) 级别
查询结果就是 \(\max \{f_{L,2^k},f_{R-2^k-1k,k}\}\)

至于 \(k\),肉眼可见 \(k=\lfloor\log _2 (len)\rfloor\)
此处可以直接使用 cmath 库中的 log() 函数,它是用来求以 10 为底的对数的 根据换底公式1可知 \[k=\lfloor\log_2(len)\rfloor=\lfloor \frac{\lg(len)}{\lg2} \rfloor\]

实现

首先是初始化

1
2
3
4
5
6
7
8
9
for (int j = 0; j < M; ++j) {
for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
if (!j) {
f[i][j] = w[i]; // 从 i 开始长度为 2^0=1 的区间最大值为 i 本身
} else {
f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
}
}
然后是查询
1
2
3
4
5
6
int query(int l, int r) {
int len = r - l + 1;
int k = log(len) / log(2);

return max(f[l][k], f[r - (1 << k) + 1][k]);
}

动态修改

这个标题比较诡异,因为我提到过

只支持静态区间

但是实际上我们可以用一些小 trick 实现在 st 表的尾部增加值。(前提是题目要求比较少,比如目前这道题只需要在尾部增加数,同时只需要查询尾部某长度区间的最值)
显然对于 st 表的每一个 \(f_{i,j}\) 来说,他只会用到 \(f_{k,j}\),\(k>i\) 的值而不会用到前面的值,因此我们给他做一个倒转。
换句话说,现在 \(f_{i,j}\) 表示从 \(i\) 开始,向前长度为 \(2^j\) 的区间中的最大值。
代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void add(int a) {
a += t;
a %= d;
ori[++tail] = a;
for (int j = 0; tail - (1 << j) + 1 > 0; ++j) {
if (!j) {
f[tail][j] = a;
} else {
f[tail][j] = max(f[tail][j - 1], f[tail - (1 << j - 1)][j - 1]);
}
}
}

void query(int len) {
int l = tail - len + 1;
int k = log2(len);
t = max(f[tail][k], f[l + (1 << k) - 1][k]);
}


  1. \[ \log_xy=\frac{\log_cy}{\log_cx} \]↩︎