ST表中sti定义为从下标i开始、长度为2^j的区间最值，是为了支持O(1)查询：任意[l,r]可被两个长度2^k（k=⌊log₂(r−l+1)⌋）的重叠子区间[l,l+2^k−1]和[r−2^k+1,r]完全覆盖，从而通过查表取max/min得解。
ST 表（Sparse Table）能真正实现 O(1) 区间最小值查询，但预处理必须用动态规划、不能只靠递归，且数组下标和 log 预处理方式稍有不慎就会越界或查错。
为什么 st[i][j] 表示的是从 i 开始、长度为 2^j 的区间的最小值
这是 ST 表定义的核心：不是“左端点+右端点”，而是“起点+长度幂次”。这样设计是为了让任意区间 [l, r] 能被两个长度为 2^k 的重叠区间完全覆盖（k = floor(log2(r-l+1))）。如果误定义成 st[l][r] 或按 1
预处理时需保证：j 从 1 开始枚举（j=0 是原数组），i 上界为 n - (1 ，否则 <code>i + (1 会越界。
常见错误现象：st[5][3] 访问非法内存、查询结果比实际最小值大、对长度为 1 的区间返回随机值。
立即学习“C++免费学习笔记（深入）”；
-
st[i][0] = a[i]（0-indexed 原数组） st[i][j] = min(st[i][j-1], st[i + (1- 二维数组第二维大小至少为
log2(n)+1，建议直接开20（支持n ≤ 1e6）
如何安全计算 log2 并避免浮点误差
C++ 标准库 log2 返回 double，对整数输入如 log2(8) 理论上是 3，但实际可能是 2.9999999，floor 后变 2，导致查询区间拆分错误。生产代码中绝不能直接用 (int)floor(log2(len))。
正确做法是预处理一个 log2_table 数组，或用位运算：
int len = r - l + 1; int k = 31 - __builtin_clz(len); // GCC 内置函数，返回最高位位置（即 floor(log2(len))） // 或手动打表： // log2_table[1] = 0; for (int i = 2; i <= n; ++i) log2_table[i] = log2_table[i/2] + 1;
注意：__builtin_clz(0) 是未定义行为，务必确保 len > 0；若用打表，数组大小要 ≥ n+1。
查询 query(l, r) 时两个子区间为何必须重叠而非拼接
因为 ST 表只支持长度为 2 的幂的区间，而任意 len = r-l+1 不一定是 2 的幂。正确做法是取最大 k 满足 2^k ≤ len，然后用 [l, l+2^k-1] 和 [r-2^k+1, r] 这两个长度为 2^k 的区间覆盖整个 [l, r] —— 它们一定重叠，且并集正好是 [l, r]。
错误写法：min(st[l][k], st[l+(1（这是拼接，仅当 <code>len == 2^(k+1) 才对）；或漏掉 +1 导致右区间起点偏移。
- 正确查询逻辑：
int k = log2_table[r - l + 1]; return min(st[l][k], st[r - (1 - 务必确认
l和r是 0-indexed，且st数组已按该索引方式填充 - 若输入是 1-indexed 查询，先统一转成 0-indexed 再查
内存与初始化陷阱：二维 vector 还是静态数组
ST 表空间复杂度是 O(n log n)，对 n = 1e5，log n ≈ 17，需要约 1.7e6 个 int —— 用 vector<vector>></vector> 动态分配容易慢且易错（比如内层 vector 大小不一致）。更稳的方式是用一维数组模拟二维，或直接开静态二维数组。
例如：int st[MAXN][20];（MAXN = 100010），全局定义后自动清零；若用 vector，必须显式 resize 每一行，且注意第二维大小固定。
另一个坑：多次调用 RMQ 前忘记重新初始化 st 数组，残留旧数据导致查询错误。尤其在多测试用例场景下，每次预处理前应确保 st[i][0] 正确赋值。
边界最易忽略的一点：当 n = 1 时，j 循环不应执行（因为 1 n 对所有 j ≥ 1 成立），否则 i 枚举范围为空，但 st 第二维若未初始化，query 可能读到脏值。
