核心逻辑与数学原理
1. 问题背景
给定一个长度为 $N$ 的固定序列，进行 $M$ 次区间最值查询（RMQ）：
- 朴素做法：每次查询都遍历一遍区间 $[L, R]$，单次查询时间复杂度为 $O(N)$，总时间复杂度为 $O(M \times N)$。在面对大规模数据时会彻底超时。
- ST 表方案：预处理log数组$O(N)$，建f表 $O(N \log N)$，单次查询仅需 $O(1)$，总时间复杂度优化至 $O(N \log N) + M$。
2. 幂等性与可重复贡献
ST 表（Sparse Table）的本质是基于动态规划思想的倍增算法，用于解决静态区间最值查询问题。
其数学基石在于覆盖可重复贡献性质（Idempotent Operations），即对于任意满足 $x * x = x$ 的二元幂等运算符 $*$（如 $\max, \min, \gcd$ 以及位运算中的 $\&, |$），多个重叠子区间的运算结果等于其并集的运算结果。
概念拆解：“幂”指乘方，“等”指相等。幂等的字面意思就是“高次幂的结果与一次幂相同”。其核心思想是：操作一次和操作无数次，最终结果完全一样。
3. 常数级空间覆盖
对于任意查询区间 $[L, R]$，其长度为 $len = R - L + 1$。令 $k = \lfloor \log_2(len) \rfloor$。
由于满足 $2^k \le len < 2^{k+1}$，区间 $[L, R]$ 必然能被两个长度为 $2^k$ 且分别以 $L$ 为起点、 $R$ 为终点的子区间完全覆盖（中间允许重叠）。其集合关系表示为：
$$[L, R] = [L, L + 2^k - 1] \bigcup [R - 2^k + 1, R]$$
基于幂等性，重叠部分不会影响最终的最值结果。由此，整个 RMQ 查询简化为常数级的代数映射，直接达成 $O(1)$ 查询：
$$\text{RMQ}(L, R) = \max(f[L][k], f[R - 2^k + 1][k])$$
状态设计与算法推导
1. 状态定义与倍增递推
在状态定义中：
- 第一维 $i$ 映射序列下标，边界为 $N$。
- 第二维 $j$ 映射 $2$ 的幂次，边界为 $\lfloor \log_2 N \rfloor$。
设 $f[i][j]$ 表示区间 $[i, i + 2^j - 1]$ 长度为 $2^j$ 的子区间最值。利用倍增思想，当前状态（长度为 $2^j$ 的大区间）由上一层 $j-1$ 阶段的两段长度为 $2^{j-1}$ 的子区间递推合并（翻倍）而来：
- 左半区间：$[i, i + 2^{j-1} - 1]$
- 右半区间：$[i + 2^{j-1}, i + 2^j - 1]$
状态转移方程为：
$$f[i][j] = \max(f[i][j-1], f[i + 2^{j-1}][j-1])$$
2. 拓扑序与循环顺序
在编写预处理代码时，外层循环必须枚举幂次 $j$，内层循环枚举下标 $i$。
计算当前层 $j$ 的大区间状态，必须依赖于上一层 $j-1$ 已经计算完毕的小区间状态。
3. $\log$ 数组常数级优化
为了在查询阶段真正达成 $O(1)$ 的极致速度，必须消除循环迭代，并避免直接调用高代价且存在精度风险的数学库 std::log2() 函数。
推荐的做法是在预处理阶段，通过线性时间 $O(N)$ 递推计算出 $1 \sim N$ 所有可能区间的 $\log_2$ 下取整值。查询时直接查表即可：
// 预处理 log 数组
lg[1] = 0;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
通过上述优化，在查询时仅需执行 int k = lg[len];，即可完美保障常数级响应。
const int MAXN = 100005; // 根据题目数据范围调整
const int MAXJ = 21; // log2(MAXN) + 2
int n;
int a[MAXN];
int lg[MAXN];
int st[MAXN][MAXJ];
// ST 表预处理：O(N log N)
void init() {
// 1. 线性递推预处理 log 数组
lg[1] = 0;
for (int i = 2; i <= n; i++) {
lg[i] = lg[i >> 1] + 1;
}
// 2. 注入 DP 初始状态（1-indexed）
for (int i = 1; i <= n; i++) {
st[i][0] = a[i];
}
// 3. 核心倍增 DP：外层枚举幂次，内层枚举下标
for (int j = 1; j <= lg[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
// O(1) 区间最值查询
inline int query(int l, int r) {
int len = r - l + 1;
int k = lg[len];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}NOIP 实战避坑指南
- 循环顺序颠倒与边界溢出
- 循环颠倒：预处理建表时，外层必须枚举幂次 $j$，内层枚举下标 $i$。由于状态转移方程中
st[i][j]强依赖于上一层状态st[i + (1 << (j - 1))][j - 1]，若 $i$ 在外层，计算当前状态时所需的更大下标处的小区间状态尚未被扫到，直接破坏了动态规划的拓扑序，导致算法读入未初始化的内存垃圾值。 - 边界溢出：在 1-indexed 体系下，内层循环的循环条件必须严格限制为
i + (1 << j) - 1 <= n。缺失边界控制或误写为< n，会导致数组横向越界，在评测机上极易踩中段错误（SIGSEGV）或引发诡异的内存污染。
- 位运算优先级与常数灾难
- 优先级陷阱：区间覆盖查询中，右半区间的起点为
r - (1 << k) + 1。由于加减运算符的优先级高于移位运算符，如果漏掉括号写成r - 1 << k + 1，其实际执行逻辑会变为(r - 1) << (k + 1)，导致查询范围彻底变形。在任何涉及位运算的混合表达式中，务必加满括号。 -
常数灾难：严禁在建表或查询阶段高频调用
<cmath>库中的std::log2()函数。该函数面向浮点数设计，涉及 FPU 浮点指令转换且存在潜在精度风险。其巨大的常数开销在 $10^6$ 级别的高频查询下，会直接拖垮 $O(1)$ 的理论优势，导致程序因 TLE。采用 $O(N)$ 数组线性递推打表，实现纯粹的整型常数级查表。
经典 NOIP/洛谷 真题
洛谷 P3865 【模板】ST 表
- 题意描述：给定一个长度为 $N$ 的序列及 $M$ 组询问，每组询问要求输出区间 $[L, R]$ 内的最大值。数据范围：$N \le 10^5$，$M \le 2 \times 10^6$。
- 问题本质与核心思路：静态区间最值查询的标准模板。任何线段树或树状数组的 $O(M \log N)$ 方案在此题极大的询问量（$2 \times 10^6$）下均会面临严重的 TLE 卡常风险。解题本质是运用倍增法预处理出所有 $2^j$ 长度的区间最值，利用幂等性通过常数级空间重叠覆盖完成 $O(1)$ 响应。
核心算法代码
// P3865 核心代码：单指标最大值 ST 表
int lg[MAXN], st[MAXN][MAXJ];
void init(int n, int a[]) {
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) st[i][0] = a[i];
for (int j = 1; j <= lg[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int query(int l, int r) {
int k = lg[r - l + 1];
return max(st[l][k], st[r - (1 << k) + 1][k]);
}
洛谷 P2880 [USACO07JAN] Balanced Lineup G
- 题意描述：给定每天的奶牛身高序列，多次询问某个特定区间内最高奶牛与最矮奶牛的身高差。数据范围：$N \le 5 \times 10^4$，$M \le 2 \times 10^5$。
- 问题本质与核心思路：多指标静态 RMQ 问题。问题的本质是同时维护区间最大值与区间最小值。由于静态不涉及修改操作，只需建立两个独立的 ST 表分别维护 $\max$ 和 $\min$。查询时分别以 $O(1)$ 读出两表结果，作差即可。
核心算法代码
// P2880 核心代码：双指标最大/最小值 ST 表
int lg[MAXN];
int st_max[MAXN][MAXJ], st_min[MAXN][MAXJ];
void init(int n, int a[]) {
lg[1] = 0;
for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= n; i++) st_max[i][0] = st_min[i][0] = a[i];
for (int j = 1; j <= lg[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st_max[i][j] = max(st_max[i][j - 1], st_max[i + (1 << (j - 1))][j - 1]);
st_min[i][j] = min(st_min[i][j - 1], st_min[i + (1 << (j - 1))][j - 1]);
}
}
}
inline int query_diff(int l, int r) {
int k = lg[r - l + 1];
int mx = max(st_max[l][k], st_max[r - (1 << k) + 1][k]);
int mn = min(st_min[l][k], st_min[r - (1 << k) + 1][k]);
return mx - mn;
}