ST 表（sparse table）

ST 表是一种基于倍增维护区间最大值、最小值、区间 $\gcd$ 等问题的一种数据结构。它不支持修改，却换来了 $\Theta(1)$ 查询的时间复杂度。它唯一的问题在于它只能计算可重复计算贡献问题，即满足以下性质的 $\mathrm{func}$：

$$\forall a\in\mathbb{R},\mathrm{func}(a,a)=a$$

我们发现线段树可以维护这种信息，但是查询时间复杂度是 $\Theta(\log n)$ 的。

先介绍几个概念：

倍增

用于快速幂。我之前在快速阶乘算法里已经涉及到了倍增。

RMQ 问题

RMQ 问题指区间最值问题（Range Maxinum/Mininum Query）。由于 $\mathrm{min,max}$ 都是可重复计算贡献问题，所以可以使用 ST 表在 $\Theta(1)$ 的时间复杂度内完成查询。

步入正题

ST 表需要预处理，时间复杂度为 $\Theta(n\log n)$。

说句闲话：我们对两个区间进行合并。我们应该如何合并？

假设两个区间为 $\lbrack l,l+2^k)$ 和 $\lbrack l+2^k,l+2^{k+1})$，我们很明显就可以将两个区间通过一次 $\mathrm{func}$ 得到 $\lbrack l,l+2^{k+1})$ 的结果。

我们令 ST 表的 table[k][l] 维护区间 $\lbrack l,l+2^{k})$ 的结果，即得转移方程：

$$table\lbrack k\rbrack\lbrack l\rbrack=\mathrm{func}(table\lbrack k-1\rbrack\lbrack l\rbrack,table\lbrack k-1\rbrack\lbrack l+2^{k-1})\rbrack) $$

于是预处理时间复杂度为 $\Theta(n\log n)$。

---

然后是查询操作。我们设查询的区间为 $\lbrack l,r)$。

然后我们设 $k=\log(r-l)$。我们发现，由于 $\mathrm{func}$ 是可重复计算贡献问题的函数，我们可以得到

$$\begin{aligned} ans_{\lbrack l,r)}&=\mathrm{func}(ans_{\lbrack l,l+2^k)},ans_{\lbrack r-2^k,r)})\\ &=\mathrm{func}(table\lbrack k\rbrack\lbrack l\rbrack,table\lbrack k\rbrack\lbrack r-2^k\rbrack)\\ \end{aligned} $$

时间复杂度 $\Theta(1)$ 。完结撒花。