ST表预处理必须用log₂(i)向下取整，因为fi定义为[i, i+2^j−1]区间最值，查询[l,r]时需取最大k使2^k≤r−l+1，即k=⌊log₂(r−l+1)⌋；若向上取整或浮点截断错误（如log2(65536)返回15.9999→int得15），会导致覆盖不足或越界。
ST表预处理为什么必须用log2(i)向下取整
因为ST表的f[i][j]定义为从位置i开始、长度为2^j的区间的最大值，而任意区间[l, r]要被两个长度为2^k的重叠子区间覆盖，其中k = floor(log2(r - l + 1))。如果向上取整或四舍五入，会导致覆盖长度不足或越界。
常见错误是写成int k = log2(r - l + 1)——这在C++中log2返回double，浮点误差可能让65536变成15.999999，int截断后变15，查出来的结果就错了。
- 正确做法：用
31 - __builtin_clz(r - l + 1)（GCC，适用于正整数） - 或预处理
log2_table数组：for (int i = 2; i - 别用
std::log2做索引计算，除非加round()并确保输入不为0
线段树build时递归边界写错导致query返回0或随机值
典型错误是把建树的区间写成[l, r]但递归调用写成build(l, mid)和build(mid+1, r)，却忘了mid = (l + r) / 2在整数除法下可能等于l，当l == r时没终止——栈溢出或访问越界。
更隐蔽的问题是节点存储方式：若用vector<int> tree</int>且按1为根，左儿子是2*node，那数组大小至少要是4 * n。开2 * n在查询时大概率踩到未初始化内存，返回0或脏值。
立即学习“C++免费学习笔记（深入）”；
- 务必检查
if (l == r) { tree[node] = a[l]; return; }是否在递归前 - 数组大小宁可多开：用
tree.resize(4 * n)，别信“理论2n就够” - query函数里若用
if (r qr)，注意边界是闭区间还是左闭右开——RMQ通常用闭区间[l, r]，别混用
ST表比线段树快，但不支持修改，连单点更新都不行
ST表本质是静态DP：f[i][j] = max(f[i][j-1], f[i + (1 。所有状态依赖于初始数组，一旦某个<code>a[i]变了，整个f[i][*]和所有覆盖i的f[k][j]都要重算——复杂度退化为O(n log n)，比暴力还差。
所以“支持区间最大值查询”这个需求，得先问清楚：有没有后续修改？有没有强制在线？有没有空间限制？
- 纯离线批量查询（如OJ上一道题只读一次数组，查1e5次）→ 无脑用ST表，预处理
O(n log n)，每次查询O(1) - 有单点更新或区间更新 → 只能上线段树，或考虑分块（
O(sqrt(n))查询+更新） - 内存极度紧张（比如嵌入式）且查询极少 → 直接遍历区间，
O(n)单次也比建ST表省空间
ST表二维数组怎么开才不MLE（尤其n=1e6时）
n = 1e6时，j最大是log2(1e6) ≈ 20，所以f[n][21]理论上要1e6 * 21 * sizeof(int) ≈ 84MB，超多数OJ内存限制（64MB常见）。
关键优化是滚动第二维：ST表DP时j只依赖j-1，可以只存两层；但更常用的是用vector<vector>></vector>配合reserve，或直接一维化：
vector<int> f(n * LOGN); #define F(i, j) f[(i) * LOGN + (j)]
不过最实用的方案是：别存满n × LOGN，对每个i只存到最大合法j（即满足i + (1），用<code>vector<vector> > f(n)</vector>，然后f[i].resize(max_j_i + 1)。内存能省30%以上。
- 别用
int f[1000000][21]——全局数组会进BSS段，容易编译失败 - LOGN建议定义为
20或21，别用ceil(log2(n))实时算，宏或const即可 - 如果n不确定但上限已知（如
#define MAXN 1000000），就按上限开，别试图动态推导维度
实际写的时候，ST表的常数远小于线段树，但那个二维内存布局和log预处理的细节，比想象中更容易出错。尤其是从调试器里看到f[0][0]是对的，f[0][1]却是0——八成是mid算错或边界没卡死。
