ST 表学习笔记

本文章最后更新日期为:2021-08-25

ST 表是什么

简单来说,ST 表就是一个二维数组,使用这个数组来存储需要的信息。

ST 表能干什么

ST 表主要用来处理静态区间的 RMQ 问题。

其他可用 ST 表处理的问题:

  • 最大公因数(gcd)
  • 最小公倍数(lcm)
  • 可重复贡献问题
  • \cdots

所谓 RMQ 问题指的是区间的最大 / 最小值查询(Range Maximum/Minimum Query)。

朴素的 RMQ 问题算法时间复杂度为 O(n2)O(n^{2}),而使用 ST 表可以做到 O(nlogn)O(n\log{n}) 预处理、O(1)O(1) 查询。

怎么使用 ST 表

二维数组的开辟

由于 ST 表使用了倍增的思想,所以创建的二维数组十分 “有精神”

1
int32_t st[MAX_N][(int32_t)std::log2(MAX_N) + 1];

含义:st[i][j] 表示在区间 [i,i+2j)\left[i, i + 2^{j}\right) 中的最大值 / 最小值。
即:

sti,j=RMQ(i,i+2j1)st_{i,j} = \text{RMQ}(i, i + 2^{j} - 1)

由于 sti,0st_{i, 0} 表示 RMQ(i,i+201)\text{RMQ}(i, i + 2^{0} - 1),所以可以将原序列存入 sti,0st_{i, 0}

预处理

code(以最大值为例):

1
2
3
4
5
for (int32_t p = 1; p <= (int32_t)std::log2(MAX_N); ++p) {
for (int32_t i = 1; i + (1 << p) <= n + 1; ++i) {
st[i][p] = std::max(st[i][p - 1], st[i + (1 << (p - 1))][p - 1]);
}
}

由于我们计算倍增时需要使用到上一级计算的结果,所以将 p 放在最外层循环。

为了计算 sti,pst_{i, p},需要知道 sti,p1st_{i, p-1}sti+2p1,p1st_{i + 2^{p - 1}, p - 1}

他们之间的关系如下(以 st1,2st_{1, 2} 为例):

st1,2=max(st1,1,st3,1)st_{1, 2} = \max\left(st_{1, 1}, st_{3, 1}\right)

s1s2st1,1s3s4st3,1st1,2s5sn\underbrace{\overbrace{s_{1} \quad s_{2}}^{st_{1, 1}} \quad \overbrace{s_{3} \quad s_{4}}^{st_{3, 1}}}_{st_{1, 2}} \quad s_{5} \quad \cdots \quad s_{n}

这样是不是就很显然了?

查询

当我们需要查询 RMQ(l,r)RMQ(l, r) 时,需要寻找两个区间 [l1,l1+2k1)\left[l_{1}, l_{1} + 2^{k_{1}}\right)[l2,l2+2k2)\left[l_{2}, l_{2} + 2^{k_{2}}\right) ,使得这两个区间的并集刚好为 [l,r]\left[l, r\right]

为什么是并集?为什么中间不能断开或者超过 [l,r]\left[l, r\right]

  • 并集是因为在 stl1,l1+2k1st_{l_{1}, l_{1} + 2^{k_{1}}} 中保存了最值,而在 stl2,l2+2k2st_{l_{2}, l_{2} + 2^{k_{2}}} 中也保存了最值,所以将他们取并集刚好能够满足 [l,r]\left[l, r\right] 时只需要对这两个值再取最值即可。
  • 不能断开因为如果 [l,r]\left[l, r\right] 中间有一部分为包含在并集内就无法判断整个 [l,r]\left[l, r\right] 内的最值。
  • 不能超过 [l,r]\left[l, r\right] 是因为一旦并集包含了 [l,r]\left[l, r\right] 以外的区域,那么这个并集内的最值同样为整个区域的最值而不是 [l,r]\left[l, r\right] 内的最值。

所以我们需要

l1ll2+2k2r+1l_{1} \gets l \newline l_{2}+2^{k_{2}} \gets r + 1

在此基础上使 l1+2k1l_{1}+2^{k_{1}} 尽量靠近 rr,使 l2l_{2} 尽量靠近 ll

由于预处理 ST 表时已经处理出所有的 sti,k,k[0,log2MAX_N]st_{i, k}, k \in \left[0, \log_{2}{MAX\_N}\right]。所以我们直接将 l1l_{1} 设为 ll,现在只需要尽量使得 l1+2k1l_{1}+2^{k_{1}} 靠近 rr 即可。

那么可以使用对数计算这个区间的长度,即

k1=log2(rl+1)k2=k1k_{1} = \log_{2}(r - l + 1) \newline k_{2} = k_{1}

log\log 是啥?

我们已经学过幂运算,形如 aba^{b},那么如果我们知道幂运算的结果和底数如何知道指数呢?

没错,通过对数运算,我们就可以知道指数了。

logaab=b,a0\log_{a}{a^{b}} = b, a \neq 0

code:

1
2
3
4
int32_t query(const int32_t l, const int32_t r) {
int32_t k = std::log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}

最后仍然是亿些练习

其实基本上滑动窗口 / 单调队列的题都可使用 ST 表(时间允许的情况下)

  • 洛谷 P3865 【模板】ST 表
  • 洛谷 P2880 [USACO07JAN] Balanced Lineup G
  • 洛谷 P1816 忠诚
  • 洛谷 P1886 滑动窗口 /【模板】单调队列