线段树比树状数组更直接支持RMQ：BIT原生不支持区间最值查询，需复杂改造；线段树天然支持，建树和查询均为O(n)和O(log n)，逻辑清晰且易验证正确性。
线段树做RMQ比树状数组更直接
树状数组（BIT）原生只支持前缀和类操作，想查任意区间 [l, r] 的最大值，它没法像求和那样用 query(r) - query(l-1) 拆解——因为 max(a, b) - max(c, d) 没有意义。所以严格来说，标准 BIT 不能直接做 RMQ。有人改造成“正向+反向双BIT”或“稀疏表+BIT辅助”，但已脱离其设计本意，代码复杂度和常数反而更高。
线段树则天然支持区间最值查询：每个节点存对应区间的 max_val，合并时取左右子节点最大值，建树和查询都是 O(n) 和 O(log n)，逻辑清晰、边界可控。
- 别硬套
BIT做 RMQ，除非题目强制限定空间且数据静态、离线、可离散化+预处理 - 若真要用
BIT，得配合额外结构（如每个位置维护一个单调栈），实际编码量不比线段树少 - 线段树的懒标记（
lazy）在带更新的 RMQ 场景下也比 BIT 改造方案更容易验证正确性
线段树实现 RMQ 要避开三个典型坑
写完发现结果错？大概率掉进以下任一陷阱：
-
build时递归终止条件写成l == r是对的，但若数组从 0 开始而节点编号从 1 开始，tree[idx] = arr[l]中的l必须是原始数组下标，不是节点编号 -
query中区间不交时（如r < tl || l > tr）必须返回极小值（如INT_MIN），而不是 0 或nullptr；否则干扰max()合并 - 更新操作中，若用“点更新 + 自底向上更新父节点”，漏掉某一层的
tree[idx] = max(tree[2*idx], tree[2*idx+1])，就会导致后续查询失效
示例片段（关键判断）：
立即学习“C++免费学习笔记（深入）”；
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
int query(int idx, int tl, int tr, int l, int r) {
if (r < tl || l > tr) return INT_MIN; // 必须这句
if (l <= tl && tr <= r) return tree[idx];
int tm = (tl + tr) / 2;
return max(query(2*idx, tl, tm, l, r),
query(2*idx+1, tm+1, tr, l, r));
}
静态 RMQ 用 Sparse Table 更快，但不支持修改
如果输入数组完全不变，且查询次数远大于建表开销，ST 表（稀疏表）是更优选择：预处理 O(n log n)，单次查询 O(1)，无递归、无函数调用开销，缓存友好。
-
st[i][j]表示从下标i开始、长度为2^j的区间的最大值 - 查询
[l, r]时，令len = r-l+1，找最大k满足2^k <= len，答案就是max(st[l][k], st[r-(1<<k)+1][k]) - 不支持单点修改——哪怕改一个数，整个
st表都要重建，时间退化回O(n log n)
所以“是否支持更新”是选线段树还是 ST 的分水岭，不是看谁写起来短。
实际项目里别手写线段树，优先用 std::ranges::max_element 或分块
竞赛题才要求手写完整线段树。真实业务中，90% 的区间最值需求其实没那么极端：
- 若数组小（
n < 5000）、查询少（< 1000次），直接用std::max_element(arr+l, arr+r+1)，代码零出错风险，CPU 缓存还更友好 - 若
n ~ 1e6且需中等频次查询（几百次），分块（sqrt decomposition）比线段树更好调：每块存最大值，查询时整块取block_max，两端暴力扫，实现简单、常数小、容易 debug - 只有当
n > 1e6、查询上万次、且存在频繁单点更新时，手写线段树才真正必要
线段树的调试成本被严重低估：指针越界、区间合并逻辑错、懒标记传播遗漏……这些 bug 在小数据上不暴露，上线后随机崩。
