ST表总结
原理
基于倍增的思想。
RMQ模板
ST表的应用
区间最值、区间GCD、区间按位与、区间按位或。
优缺点
不支持修改，维护信息有限。
二维ST表
一般是维护正方形的最值
令
f
[
i
]
j
k
f[i][j][k]
f[i][j][k]表示以
(
,
)
(i,j)
(i,j)为左上角边长为
2
2^k
2k的矩形的最大值。
有递推式：
=
max
{
−
1
+
}
\large f_{i,j,k}=\max\{f_{i,j,k-1},f_{i+2^{k-1},j,k-1},f_{i,j+2^{k-1},k-1},f_{i+2^{k-1},j+2^{k-1},k-1}\}
fi,j,k=max{fi,j,k−1,fi+2k−1,j,k−1,fi,j+2k−1,k−1,fi+2k−1,j+2k−1,k−1}
若题目求固定边长
n
n的最值，则可以省去第三维，递推到
≥
2^{k+1}\ge n
2k+1≥n即可。