ST 表（RMQ 问题）
XingnoYi
·
·
算法·理论
\text{ST} 表
对于 \text{RMQ} （求区间最值）问题，若需要修改，则需要使用线段树。
若无需修改，则常常使用 \text{ST} 表，运行效率更高。
一、核心思想：
构建 \text{ST} 表的核心在于倍增和 DP。
如下以区间最大值为例讲解。
P1：一维 \text{ST} 表。
1. 定义：
f_{i,j} 表示以第 i 个数作为左端点，长度为 2^j 的区间中的最值。即 [i,i + 2^j -1] 的区间最值，区间总长度为 2^j。
2. 转移（预处理）：
转移类似于二分思想。
如图，我们将一个长度为 2^j 的区间分成 2 个长度为 2^{j-1} 的子区间，整个区间的最值可由两个子区间得到。
按照 j 的顺序 DP，我们可以得到如下转移： \begin{cases}
a_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (j = 0) \\
\max(f_{i,j-1},f_{i+2^{j-1},j-1})\ (j > 0)
\end{cases}
其时间复杂度为 O(n \log n)。
3. 询问：
同样的，基于二分思想，做到 O(1) 询问。
给出区间 [l,r]，其长度为 len，如何将区间分成两部分？
根据 f 数组的定义，这两个区间的长度应为 2^k， k = \left \lfloor \log_2(len) \right \rfloor 。
也就是分成 2 个长为 2^{\left \lfloor \log_2(len) \right \rfloor} 的子区间。
显然，这两个区间有重合。
左区间与右区间的长度和为 2^{k+1}，区间长度 len= 2^k+a\ (a < 2^k)，所以不会有元素遗漏。
\text{ans} = \max(f_{l,k},f_{r-2^k+1,k})
4. 优化：
令 $Log_0 = -1$，则：
$$ Log_i = Log_{i/2}+1 $$
### 5. 模板与例题：
**[一维 ST 表模板](https://www.luogu.com.cn/paste/211ptavz)。**
1. [【模板】ST 表](https://www.luogu.com.cn/problem/P3865)。
2. [忠诚](https://www.luogu.com.cn/problem/P1816)。
3. [质量检测](https://www.luogu.com.cn/problem/P2251)。
4. [[SCOI2007] 降雨量](https://www.luogu.com.cn/problem/P2471)。
5. [奶牛排队](https://www.luogu.com.cn/problem/P6510)。
## P2：二维 $\text{ST}$ 表。
**类似于一维 $\text{ST}$ 表。**
### 1. 定义：
**$f_{i,j,a,b}$ 表示左上角为 $(i,j)$ ，右下角为 $(i+2^a -1,j+2^b -1)$ 的矩阵的最值。**
### 2. 转移（预处理）：
考虑把询问矩阵划分为 $4$ 个可能重叠的子矩阵来转移。\
$f_{i,j,a,b} = \begin{cases}
a_{i,j}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (a=b=0) \\
\max(f_{i,j,a-1,b},f_{i+2^{a-1},j,a-1,b})\ (a > 0) \\
\max(f_{i,j,a,b-1},f_{i,j+2^{b-1},a,b-1})\ \ (b > 0)
\end{cases}
通俗地说，就是横着二分转移一遍，再竖着二分转移一遍。
3. 询问：
设：
k_1 = \left \lfloor \log_2(x_2 - x_1 + 1) \right \rfloor
k_2 = \left \lfloor \log_2(y_2 - y_1 + 1) \right \rfloor
所以原询问矩阵可以看成 4 个长为 2^{k_1}，宽为 2^{k_2} 的矩阵来转移（如图，标出了 4 个矩阵左上起点的坐标）。
则：
\text{ans} = \max(f_{x_1,y_1,k_1,k_2}, f_{x_2-2^{k1}+1,y_1,k_1,k_2}, f_{x_1,y_2-2^{k2}+1,k_1,k_2}, f_{x_2-2^{k1}+1,y_2-2^{k2}+1,k_1,k_2})
4. 模板与例题：
- [HAOI2007] 理想的正方形。