因为j必须是整数，而2^j需不超过查询区间长度r−l+1，故取满足2^j≤r−l+1的最大整数j，即j=⌊log₂(r−l+1)⌋；若四舍五入可能导致2^j>r−l+1，使区间越界。
ST表预处理为什么必须用 log2 向下取整而非四舍五入
因为 ST[i][j] 定义为从位置 i 开始、长度为 2^j 的区间的最大值，j 必须是整数，且要满足 i + 2^j - 1 。若对 <code>log2(len) 四舍五入（比如 len=5 时得 j=2），会导致区间越界或覆盖不全；向下取整（floor(log2(len))）才能保证 2^j ≤ len，后续用两个重叠区间拼出任意查询才安全。
实操建议：
- 用
int j = 31 - __builtin_clz(len)（GCC）或static_cast<int>(std::log2(len))</int>（注意浮点误差，建议配合while ((1 校验） - 预处理时外层循环
i（起点），内层循环j（幂次），上限为j_max = floor(log2(n)) + 1 - 常见错误：把
j循环写成for (j = 1; j —— 这会越界且逻辑错乱
线段树单次查询为何比 ST 表慢一个 log n 常数级
ST 表查 [l, r] 是纯计算：算出 k = floor(log2(r-l+1))，然后返回 max(ST[l][k], ST[r-(1，共 2 次数组访问 + 若干位运算；线段树则需递归或迭代遍历 <code>O(log n) 个节点，每次都要判断区间交叠、分支跳转，cache 不友好。
实操建议：
- 静态数组实现的 ST 表在
n ≤ 1e6时，预处理O(n log n)空间可接受，查询稳如O(1) - 线段树适合动态更新场景；若全程只查不改，ST 表几乎总是更快 —— 即使
n=1e5，ST 表查询耗时通常不到线段树的 1/3 - 别用指针版线段树做 RMQ 对比测试，指针跳转开销会掩盖算法差异
std::vector<:vector>></:vector> 实现 ST 表容易触发什么内存问题
二维 vector 的每行单独分配，导致 ST[i][j] 访问时 cache miss 高；更严重的是，当 n=1e6，j_max ≈ 20，总元素约 2e7，但 vector 的动态扩容 + 冗余容量会让实际内存占用翻倍，还可能因碎片化引发分配失败。
实操建议：
- 改用一维数组模拟二维：分配
vector<int> st(n * j_max)</int>，用st[i * j_max + j]替代ST[i][j] - 或直接
new int[n * j_max]（记得delete[]），避免 vector 构造/析构开销 - 常见错误：写
vector<vector>> st(n, vector<int>(j_max))</int></vector>—— 看似简洁，实测在n=5e5时比一维慢 40% 以上
离线批量查询时 ST 表的 log2 计算怎么优化
每次查都调用 log2(r-l+1) 是热点瓶颈，尤其在 glibc 下 std::log2 是通用浮点函数，延迟高；而实际 len ∈ [1, n]，完全可预处理所有可能长度的 k 值。
实操建议：
- 声明全局数组
int lg[1000001]，预处理：for (int i = 2; i - 查询时直接
k = lg[r-l+1]，零开销 - 若查询长度固定（如全是长度为 100 的区间），甚至可以建长度→
k的哈希表，但通常没必要
ST 表真正的坑不在原理，而在预处理索引边界和内存布局；线段树看似通用，但在纯静态 RMQ 场景下，它的“通用性”反而成了性能拖累。别迷信“树结构”，先看需求是否真的需要修改。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
