概念

ST 表，也称稀疏表，是用于解决可重复贡献问题的数据结构。可重复贡献问题，可理解为重叠并不改变结果。与区间和不同，如果两个区间有重叠，元素就会被重复使用，从而使答案错误。

区间最大/最小值，区间按位与/或/异或，区间 GCD 等都是可重复贡献问题，可以用 ST 表解决。

特别地，我们称区间最大/最小值的问题为 RMQ (Range Maximum/Minimum Query) 问题。

ST 表主要基于**倍增（Binary Lifting）**的思想，可以做到 $\Theta(n\log n)$ 预处理，$\Theta(1)$ 回答每个询问，但是不支持修改。

查询最大/最小值的实现

推导

设 $f(i,j)$ 表示 $[i,i+2^j-1]$ 上的最大值，有 $f(i,0)=a_i$（只有一个数）

由于区间大小正好是 $2^j$，则正好可以将区间切为大小为 $2^{j-1}$ 的左右两半，表达式分别为 $f(i,j-1)$ 和 $f(i+2^{j-1},j-1)$，只要对这两个子区间取最大值，原区间最大值也就得到了。

QQ_1736848425542.png

据此，利用递推求出 $f(i,j)$，列出转移方程：

$$ f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1)) $$

预处理

const int N = 1e5;
int Log2[N];
void init() {
	for (int i = 0; i <= n; i++) f[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j++) { // 保证区间长度 2^j 小于 n
		for (int i = 1; i + (1 << j) - 1 <= n; i++) { // 区间末尾是 i+2^j-1，保证不越界
			f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
			// 注意 j 要在外面，i 在里面
		}
	}
	// 对可能的 log_2(x) 值的预处理，之后用到
	Log2[1] = 0, Log2[2] = 1;
	for (int i = 3; i <= n; i++) {
		Log2[i] = Log2[i >> 1] + 1;
	}
}

查询