RainAir
My OI Blog
RainAir
ST表模板

O(1)求静态区间极值的算法


题目链接
在生活中,总会遇到这样一些题目:
在长度为N的数列中多次查找某区间的最大值。
于是,ST表应运而生

算法描述

ST表是一个可以在* O(nlogn) *的时间复杂度的预处理后,在 * O(1) * 的时间复杂度中查找任意区间的最大值
此算法基于倍增思想。

算法实现

此算法分预处理和查询

预处理

预处理一个st数组,对于$st[i][j]$,表示此序列第i位往后$2^j$位的最大值。
我们以最大值查询为例,预处理可以写成:
$st[i][j] = max(st[i][j-1],st[i+2^{k-1}][k-1])$
意思为区间$[i,i+2^j]$的最大值是区间$[i,i+2^{j-1}]$的最大值和区间$[i + 2{j-1},i + 2^j]$的最大值的最大值

显而易见,时间复杂度是O(nlogn)

查询

我们从预处理中可知,我们求一个区间的最大值,可以转化为求在此区间内,完全覆盖该区间的多个区间最大值的最大值
表示看不懂的看下面:
例如,我们有一个区间[1,10],我们可以通过取[1,5]和[6,10]两个区间的最大值,来找出[1,10]的最大值。但有时我们并不会运气这么好,例如我们只有[1,7]和[3,10]的最大值,但是取最大值后答案也是对的。
So,对于一个区间[l,r]我们可以算出一个数字c,让$c = log_2(r – l + 1)$,这样区间[l,r]的最大值就是$max(st[a][c],st[a – 2^b +1][c])$
然后,这就是 $O(1)$ 查询方法。

一些小问题

Q1:如何计算出$log_2(r – l + 1)$?
A1:这里在有的文章中建议你预处理出来,但这里我们选择cmath库函数

Q2:如何计算$2^j$?
A2:对于幂运算,我们选择位运算。
因为这是2的幂运算,所以能用位运算。

Q3:st表需要开多大?
A3:不需要开很大。空间复杂度仅为$nlog_2n$
即开一个$log_2n$行n列的二维数组即可。

代码实现

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/114
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

ST表模板
O(1)求静态区间极值的算法 题目链接 在生活中,总会遇到这样一些题目: 在长度为N的数列中多次查找某区间的最大值。 于是,ST表应运而生 算法描述 ST表是一个可以在* O(nlogn) *的时…
扫描二维码继续阅读
2017-11-03
标签
近期评论