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即可。