线段树不适用于纯静态RMQ，因其建树空间大（4n）、查询慢（O(log n)）、常数高且易写错；ST表预处理O(n log n)、查询O(1)，更适合静态场景；树状数组无法直接支持任意区间最值查询，因max不满足可减性。
为什么不用线段树做 RMQ？先看它卡在哪
线段树支持区间最大值查询（RMQ）和单点修改，但常数大、内存开销高：建树需 4 * n 空间，每次查询要 O(log n) 次指针跳转。在纯静态数组、只查不改的场景下，它比 ST 表 慢 2–3 倍，且代码易写错边界——比如 push_up 忘更新父节点，或查询时 mid 计算用 (l + r) / 2 导致整数溢出。
实战建议：
- 仅当需要「动态修改 + 查询」时才选线段树；否则优先用
ST 表或预处理稀疏表 - 若坚持用线段树，把
tree数组声明为vector<int>而非裸数组，避免栈溢出 - 查询函数必须严格按区间覆盖逻辑写：
if (r <= mid) return query(lc, l, mid, ql, qr);，不能漏掉ql <= l && r <= qr的完全包含剪枝
树状数组能直接做 RMQ 吗？不能，但可以绕
BIT（树状数组）原生只支持前缀和、单点更新、前缀最值，**无法直接查任意区间 [l, r] 的最大值**。常见误区是以为改一改 max 就行，结果发现 query(r) - query(l-1) 在最大值下不成立——因为 max(a,b) - max(c,d) ≠ max(a-c, b-d)。
可行的绕法（仅限静态数组）：
立即学习“C++免费学习笔记（深入）”；
- 离线处理：把所有查询按右端点排序，用
BIT维护「以 i 结尾的区间最大值」，配合扫描线，复杂度O((n + q) log n) - 双 BIT 模拟：一个存正向最大值，一个存反向最大值，查
[l, r]时拆成max( query_forward(r) - query_forward(l-1), ... )——这其实已退化为暴力，不推荐 - 真正实用的组合：用
BIT加速ST 表的构建过程（如快速求区间长度的 floor(log2(len))），但属于工程优化，非必要不加
ST 表实现 RMQ 的三个关键细节
ST 表 是静态 RMQ 的最优解：O(n log n) 预处理，O(1) 查询。但容易在以下三点翻车：
-
log2预处理必须用整数打表：运行时调std::log2会慢且有浮点误差；正确做法是开lg[1..n]数组，循环i = 2; i <= n; ++i设lg[i] = lg[i/2] + 1 -
st[0][i]存的是a[i]，不是a[i-1]；第二维长度是n，第一维长度是lg[n] + 1，别反了 - 查询时区间拆分必须用
len = r - l + 1，然后取k = lg[len]，再比较st[k][l]和st[k][r - (1<<k) + 1]；注意r - (1<<k) + 1可能越界，要确保l <= r且输入合法
实际项目中该选哪个？看修改频率和内存限制
没有银弹。如果数组初始化后从不修改，且 n ≤ 1e6，ST 表 是首选——代码短、快、稳。若 n 达到 1e7，ST 表 的 O(n log n) 内存可能爆（约 280MB），此时改用分块：每块大小 sqrt(n)，块内预处理最大值，查询时暴力扫两端 + 查块表，内存 O(n)，查询 O(sqrt(n))。
线段树只在明确需要「单点更新 + 区间查询」时启用，且务必手写非递归版本（ZKW 线段树）来压常数；树状数组别硬套 RMQ，它天生不适合。
最容易被忽略的是：所有实现都默认数组下标从 0 开始，但部分 ST 表 教程用 1-indexed，混用会导致 st[k][r - (1<<k) + 1] 计算偏移错误——检查你的 a 和 st 是否同一起始索引。
