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]。
常见错误现象：
- 写成
[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 <h3> <code>vector<vector>></vector></code> 和 <code>int f[MAXN][LOGN]</code> 哪种更稳？</h3><p>静态数组 <code>int f[MAXN][LOGN]</code> 更可靠。ST 表预处理是 O(n log n) 时间 + 空间，但 <code>vector</code> 的嵌套分配容易在栈上失败（尤其 <code>MAXN > 1e5</code>），且每次 <code>push_back</code> 可能触发多次内存拷贝，破坏缓存局部性。</p><div class="aritcle_card flexRow artxards"> <div class="artcardd flexRow"> <a class="aritcle_card_img" rel="nofollow" href="/xiazai/gongju/2823" title="C++14"><img src="https://img.php.cn/upload/manual/001/431/639/6ac8b33c327c4749.png" alt="C++14" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a> <div class="aritcle_card_info flexColumn"> <a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="overflowclass">C++14</a> <p class="overflowclass">C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。</p> </div> <a rel="nofollow" href="/xiazai/gongju/2823" title="C++14" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span> </a> </div> </div><p>使用场景与权衡：</p>
- 竞赛现场或固定上限场景：直接开全局静态二维数组，
MAXN设为100010，LOGN设为18（因2^17 = 131072 > 1e5） - 需要动态
n且内存受限：改用一维数组模拟二维，按行优先存，f[i * LOGN + j]，避免 vector 的指针跳转开销 - 千万别在函数内写
vector——局部变量占栈太大，Linux 下默认栈只有 8MB，> f(n, vector (lg[n]+1)); 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 表了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
