ST表学习笔记

RMQ

简介

区间最值问题(Range Maximum/Minimum Query,RMQ)是一类经典的区间问题,其一般形式如下:

给定一个 nn 个元素的数组 arrarr ,给定 mm 个形式为 li,ril_i,r_i 的询问,对于每个询问 iimax{arrli,arrli+2,arrli+3...,arrri}max\{arr_{l_i},arr_{l_{i+2}},arr_{l_{i+3}}...,arr_{r_i}\}

显然这种问题可以被线段树以每次询问 O(logn)O(\log n) 的时间复杂度轻松解决,但是线段树的常数较大,有时会超时。

ST表

ST表(Sparse Table,ST,又名稀疏表)可以在进行 O(nlogn)O(n \log n) 的预处理后用 O(1)O(1) 的时间复杂度处理每次RMQ(或者其他任何满足可重复贡献结合律的操作,比如区间gcd)的询问,但前提是无修改操作

原理

什么是可重复贡献问题?

可重复贡献问题 是指对于运算 optopt,满足 x opt x=xx\space opt\space x = x,则对应的区间询问就是一个可重复贡献问题。例如,最大值有 max(x,x)=xmax(x,x) = x,gcd 有 gcd(x,x)=xgcd(x,x) = x,所以 RMQ 和区间 GCD 就是一个可重复贡献问题。像区间和就不具有这个性质,如果求区间和的时候采用的预处理区间重叠了,则会导致重叠部分被计算两次,这是我们所不愿意看到的。另外, 还必须满足结合律才能使用 ST 表求解。

摘自 OI-Wiki

ST表通过倍增思想实现。

对于区间最大值问题, sti,jst_{i,j} 代表从 jj 开始 2i2^i 个数的最大值(其他操作同理,下文均以区间最大值举例)。

为什么 2i2^i 那维要放在前面?

这样能保证程序中内存访问的连续性,增加运行速度(每日一个卡常小技巧)。

ST表

ST表的建表也很好写,根据图片看出, sti,j=max{sti1,j,sti1,j+2i1}st_{i,j} = max\{st_{i-1,j},st_{i-1,j+2^{i-1}}\}

1
2
3
4
5
inline void build() {
for(int i = 1; i <= lg[n]; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}

根据"可重复贡献",查询时区间的重复是不影响结果的,所以我们可以写出查询的代码:

1
2
3
4
inline int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[k][l], st[k][r - (1 << k) + 1]);
}