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]$)将其完全覆盖。

示例

代码