st表

st表全称为sparse table，意思为稀疏表，是用于解决可重复贡献问题的数据结构。一般解决区间最大最小值（RMQ）问题。

例题

P3865 【模板】ST 表 && RMQ 问题

题目描述

求数列的静态区间最大值。

做法

时间复杂度 $O(n\log n)$ — $O(1)$ 。

预处理

$dl_i$ 为 $\lfloor\log i\rfloor$ 。 $$ dl_1=0\dl_i=dl_{\lfloor\frac{i}{2}\rfloor}+1(i>1) $$ $f_{i,j}$ 为序列第 $j$ 项到第 $j+2^i-1$ 项的最大值。

那么怎么快速地求出它呢？

$$ f_{i,j}=\max(f_{i-1,j},f_{i-1,j+2^{i-1}}) $$ $f_{i-1,j}$ 为序列第 $j$ 项到第 $j+2^{i-1}-1$ 项的最大值

$f_{i-1,j+2^{i-1}}$ 为序列第 $j+2^{i-1}$ 项到第 $j+2^i-1$ 项的最大值

这两个区间的重叠部分为第 $j+2^{i-1}-1$ 项到第 $j+2^{i-1}$ 项。

因为我们要求的是最大值，所以重叠部分对贡献是没有影响的，这类问题叫做可重复贡献问题。而求区间和是不能利用st表维护的。

时间复杂度为 $O(n \log n)$ 。

在程序中，将数组第二维表示序列第 $j$ 项要比将数组第一维表示序列第 $j$ 项跑得快（运行时间短），是因为你先枚举上面式子的 $i$ ，再枚举序列第 $j$ 项的，如果你将数组第一维表示序列第 $j$ 项，第二维表示上面式子的 $i$ ，数组指针是乱飞的，导致运行时间长，如果将数组第一维表示上面式子的 $i$ ，第二维表示序列第 $j$ 项，数组指针是连续的，运行时间短。

代码：

for(int i=1; i<=dl[n]; i++) {
    for(int j=1; j+(1ll<<i)-1<=n; j++) {
        f[i][j]=max(f[i-1][j],f[i-1][j+(1ll<<(i-1))]);  
    }
}

查询

对于每一个查询区间 $[l,r]$ ，它的长度为 $len=r-l+1$ ，那么这段区间的最大值为 $\max(f_{dl_{len},l},f_{dl_{len},r+1-2^{dl_{len}}})$ 。

读者可以按照预处理部分内容来自行发现答案为什么是这个。

时间复杂度为 $O(1)$ 。

总结

st表首先利用了倍增的思想，然后通过对长度为 $2^i$ 的区间进行预处理，最后对查询区间快速地求解，这就是st表！

时间复杂度优化

四毛子算法（Method Of Four Russians）

未完待续！