稀疏表 ST表

写在前面正文内容实现初始化过程查询 后记

写在前面

有错误请指出

正文

内容

ST表 是一个维护区间 最大值 或 最小值 的数据结构

ST表 用 $O(n\log n)$ 的时间预处理，$O(1)$ 的时间查询

设 $f[i][j]$ 表示为 下标 $i$ 起，$2^j$ 个数中的最大值，用倍增实现

很好理解

实现

本博客以最大值为例

初始化

设维护的数组为 $a[i]$ $f[i][0]=a[i]$

过程

是一个类似于 区间dp 的流程

很容易得出

$f[i][1]=max(f[i][0],f[i+1][0])$

以此类推

$f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$

就求出 ST表 了

void ST () { for (int len = 1;(1 << len) <= n;++ len) { for (int q = 1;q + (1 << len) <= n;++ q) { f[q][len] = max (f[q][len - 1] ,f[q + (1 << (len - 1))][len - 1]); } } return ; }

查询

有了 ST表 还不行，还得会查询

很容易理解

ll RMQ (int l ,int r) { int k = (int) (log ((double) (r - l + 1)) / log (2.0)); return max (f[l][k] ,f[r - (1 << k) + 1][k]); }

此处为查询 最大值

最小值同理，把 $\max$ 改为 $\min$ 即可

后记

谢谢大家

——2020.10.4