ST 表模版

正文索引 [隐藏]

简介

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

原理

预处理出原区间内长度为 1, 2, 4, \cdots, 2^k 的子区间的答案,此预处理的复杂度为 O(n \log n)
预处理的时,长度为 1 的子区间信息直接从原数组中得到。长度大于 12^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])将其完全覆盖。

示例

代码