ST 表模版

正文索引 [隐藏]

简介

给定一个长度为 $n$ 的数组,支持 $O(1)$ 查询区间最值。
使用前,调用 init() 函数初始化 ST,然后使用 query() 函数查询区间最值,下标范围从 $\left [0, n\right )$。
当前代码实现区间最小值问题,区间的最大值,最大公约数等均可以查询。

原理

预处理出原区间内长度为 $1, 2, 4, \cdots, 2^k$ 的子区间的答案,此预处理的复杂度为 $O(n \log n)$。
预处理的时,长度为 $1$ 的子区间信息直接从原数组中得到。长度大于 $1$ 为 $2^k$ 的子区间信息由两个长度为 $2^{k-1}$ 的区间合并得到。如下图中,表示 $[1, 8]$ 的橘红色区间,由两个长度为 $4$ 的灰色区间($[1,4]$, $[5,8]$)合并得到,黑色箭头表示合并操作。

查询的时候,先寻找区间覆盖查询区间的两个预处理长度为 $2^k$ 的区间,要求 $2^k$ 小于等于查询区间长度且最大,用从查询区间左侧起与右侧起的两个 $2^k$ 区间的答案组合出查询答案,单次查询复杂度 $O(1)$。
如下图,蓝色区间表示查询区间 $[3, 8]$,长度为 $6$,那么我们可以找到两个长度为 $4$ 的区间($[3, 6]$, $[5, 8]$)将其完全覆盖。

示例

代码