ST表预处理必须用log₂向下取整，因fi定义为长度2^j的区间最小值，j需为整数，故最大合法j=floor(log₂(n))；向上取整或四舍五入会导致2^j>n而越界。
ST 表预处理为什么必须用 log2 向下取整？
因为 ST 表的 f[i][j] 定义为从位置 i 开始、长度为 2^j 的区间的最小值，j 只能是整数，所以对任意区间长度 n，最大合法的 j 是 floor(log2(n))。若用 round 或向上取整，会导致 2^j > n，数组越界或覆盖无效范围。
实操建议：
- 预处理前先算好每个长度对应的
log值，存入数组lg[1..n]，避免运行时反复调用log2（浮点误差+性能差） - C++ 中推荐用位运算打表：
lg[1] = 0; for (int i = 2; i > 1] + 1; - 二维数组
f第二维大小只需开到lg[n] + 1，别直接写20或32——小数组浪费内存，大数组可能触发栈溢出（尤其本地递归环境）
查询时为何要拆成两个有重叠的子区间？
ST 表不支持任意长度的直接查，只支持长度为 2 的幂次的区间。但任意 [l, r] 都能被两个长度为 2^k 的区间完全覆盖，其中 k = lg[r - l + 1]。这两个区间分别是 [l, l + 2^k - 1] 和 [r - 2^k + 1, r]，它们一定重叠，但并集恰好是 [l, r]。
常见错误现象：
立即学习“C++免费学习笔记（深入）”；
- 写成
[l, l + 2^k - 1]和[l + 2^k, r]—— 这是线段树拆法，ST 表不能这么拆，会漏掉中间元素 - 用
k = ceil(log2(len))导致区间超出原范围，比如len=3时误取k=2，2^2=4 > 3 - 忘记加 1：计算
k时用的是r - l + 1，不是r - l
正确查询代码片段：
int k = lg[r - l + 1]; return min(f[l][k], f[r - (1 << k) + 1][k]);
vector<vector>></vector> 和 int f[MAXN][LOGN] 哪种更稳？
静态数组 int f[MAXN][LOGN] 更可靠。ST 表预处理是 O(n log n) 时间 + 空间，但 vector 的嵌套分配容易在栈上失败（尤其 MAXN > 1e5），且每次 push_back 可能触发多次内存拷贝，破坏缓存局部性。
使用场景与权衡：
- 竞赛现场或固定上限场景：直接开全局静态二维数组，
MAXN设为100010，LOGN设为18（因2^17 = 131072 > 1e5） - 需要动态
n且内存受限：改用一维数组模拟二维，按行优先存，f[i * LOGN + j]，避免 vector 的指针跳转开销 - 千万别在函数内写
vector<vector>> f(n, vector<int>(lg[n]+1));</int></vector>——局部变量占栈太大，Linux 下默认栈只有 8MB，n=1e5就崩
ST 表真能 O(1) 查询？那为什么有时比线段树还慢？
理论是 O(1)，但实际受缓存和分支影响。两次内存访问（f[l][k] 和 f[r−2^k+1][k]）若地址不连续，CPU cache miss 概率高；而线段树若实现为数组堆式且查询路径短，反而更快。
性能关键点：
- 确保
f数组按行优先存储，且j（第二维）变化最频繁——即循环顺序必须是for j ... for i ...，否则预处理时 cache 不友好 - 查询时
k是查表得来，无分支预测失败风险；但若lg[]数组未对齐或不在 L1 cache，也会拖慢 - 当查询次数远小于预处理规模（如只查 10 次），ST 表的 O(n log n) 预处理纯属浪费，此时稀疏表不如直接扫
真正体现 ST 表优势的场景：离线批量查询（≥ 1e4 次）、静态数组、内存允许预处理空间——这时候 O(1) 的常数才压得过线段树的 O(log n)。
重叠区间覆盖这个设计看着反直觉，但正是它让查询摆脱了二分或递归，成了真正意义上的两次数组访问。别试图“优化”成无重叠，那就不是 ST 表了。
