RMQ/ST表

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

下文以最大值为例说明

ST 表本质上是一个动态规划（倍增的）

先利用倍增（二进制拆分）预处理然后 $O (1)$ 查询，比线段树快，但是只支持静态区间

原理

预处理

$𝑓 𝑖, 𝑗$ 表示从 $𝑖$ 开始，长度为 $2 𝑗$ 的区间中的最大值

预处理阶段，对于 $𝑓 𝑖, 𝑗$ 来说，直接 $m a x {𝑓 𝑖, 𝑗 - 1, 𝑓 𝑖 + 2 𝑗 - 1, 𝑗 - 1}$ 递推即可，非常容易想，时间复杂度为 $O (𝑛 l o g 𝑛)$

查询

对于一个区间 $[𝐿, 𝑅]$ 来说，假设他的长度为 $𝑙 𝑒 𝑛$

很容易能找到一个 $𝑘$ 使得 $𝑙 𝑒 𝑛 2 < 2 𝑘 ⩽ 𝑙 𝑒 𝑛$

显然 $[𝐿, 𝑅]$ 被 $[𝐿, 2 𝑘], [𝑅 - 2 𝑘 - 1, 𝑘]$ 严格包含，因此 ST 表中查询最大最小值的时间复杂度是常数级别的，而不是线段树的 $l o g$ 级别
查询结果就是 $m a x {𝑓 𝐿, 2 𝑘, 𝑓 𝑅 - 2 𝑘 - 1 𝑘, 𝑘}$

至于 $𝑘$ ，肉眼可见 $𝑘 = ⌊ l o g 2 (𝑙 𝑒 𝑛) ⌋$
此处可以直接使用 cmath 库中的 log() 函数，它是用来求以 10 为底的对数的根据换底公式¹可知 $𝑘 = ⌊ l o g 2 (𝑙 𝑒 𝑛) ⌋ = ⌊ l g (𝑙 𝑒 𝑛) l g 2 ⌋$

实现

首先是初始化

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

复制

然后是查询

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 表的每一个 $𝑓 𝑖, 𝑗$ 来说，他只会用到 $𝑓 𝑘, 𝑗$ , $𝑘 > 𝑖$ 的值而不会用到前面的值，因此我们给他做一个倒转。
换句话说，现在 $𝑓 𝑖, 𝑗$ 表示从 $𝑖$ 开始，向前长度为 $2 𝑗$ 的区间中的最大值。
代码如下

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

复制

$l o g 𝑥 𝑦 = l o g 𝑐 𝑦 l o g 𝑐 𝑥$ ↩︎

本文采用 GNU 自由文档许可证许可协议，转载请注明出处。