ST表预处理必须用log₂(n)分段，因其fi表示从i开始长2^j的区间最值，需满足2^k≥(r−l+1)/2得k=floor(log₂(r−l+1))；超log₂(n)会浪费空间且越界致错。
ST表预处理为什么必须用 log2(n) 分段
因为ST表的核心是「倍增覆盖」：f[i][j] 表示从下标 i 开始、长度为 2^j 的区间的最大值。要让任意区间 [l, r] 能被两个长度为 2^k 的重叠区间完全覆盖，就必须满足 2^k ≥ (r−l+1)/2，解出来就是 k = floor(log2(r−l+1))。如果预处理时 j 超过 log2(n)，不仅浪费空间（二维数组第二维冗余），还会在查询时因越界读取未初始化内存导致结果错误。
实操建议：
- 预处理前先算
max_j = floor(log2(n)) + 1（+1 是因为 j 从 0 开始） - 用
int max_j = 0; while ((1 比调log2更安全，避免浮点误差 - 数组声明写成
int f[MAXN][LOG_MAX];，其中LOG_MAX = 20对n ≤ 1e6足够，别直接写[n][20]—— 会爆栈
线段树建树时递归终止条件容易错在哪
常见错误是把叶子节点判断写成 l == r 却没同步更新 tree[node] = a[l]，或者在非叶子节点漏掉左右子树合并逻辑。更隐蔽的问题是：当输入数组下标从 0 开始，但线段树按 1-based 区间建模（比如 build(1, 0, n-1)），此时 mid = (l + r) / 2 必须用 (l + r) >> 1 或确保不溢出，否则 l + r 在大数据下可能溢出 int。
实操建议：
- 统一用闭区间建模，建树函数签名保持为
void build(int node, int l, int r) - 终止条件只写一次：
if (l == r) { tree[node] = a[l]; return; } - 合并必须显式写：
tree[node] = max(tree[left], tree[right]);，别依赖初始化值 - 数组大小至少开
4 * n，别信“3.5*n”这种估算——边界 case 下真会越界
RMQ 查询时 ST 表比线段树快，但不能改数据
ST 表查询是 O(1)，靠的是预先算好所有 2^j 长度的极值，然后对任意 [l, r] 拆成两个固定长度的区间并取 max：max(f[l][k], f[r−(1，其中 k = floor(log2(r−l+1))。但它本质是静态结构——只要数组元素变一个，整个 f 表就失效，重算代价是 O(n log n)。而线段树支持单点修改 O(log n)，适合有 update 的场景。
实操建议：
- 纯查询高频、数据不变 → 无脑选 ST 表；哪怕 n=1e5，预处理也才 2e6 次操作
- 存在修改操作（哪怕只有几次）→ 直接上线段树，别试图给 ST 表加 lazy
- 查区间最值只是中间步骤（比如配合二分找第一个大于 x 的位置）→ ST 表更稳，避免线段树递归带来的常数抖动
ST 表查询中 __builtin_clz 替代 log2 的坑
用 int k = 31 - __builtin_clz(len) 算 floor(log2(len)) 很快，但 __builtin_clz(0) 是未定义行为，而查询长度 len = r−l+1 至少为 1，看似安全。问题出在：若编译器优化或平台差异导致 len 被误算为 0（比如 l > r 且没校验），程序就崩了。另外 __builtin_clz 参数是 unsigned int，传负数会转成大正数，结果完全不可控。
实操建议：
- 永远先断言：
assert(l - 用
len = r - l + 1后立刻转unsigned：unsigned u_len = len; - 更稳妥写法：
int k = u_len > 1 ? 31 - __builtin_clz(u_len) : 0; - 线上环境若禁用 builtin 函数，回退到预处理打表
log2_table[1..n]，比每次算log2快且确定
实际用的时候，ST 表的预处理索引和查询拆分那两步，手写错一位下标（比如 r - (1 漏了 +1）就会返回错误最大值，而且这种 bug 不报错、难调试。宁可多写两行临时变量，也别堆在一行里算。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
