线段树是区间最大值查询（RMQ）更直接可靠的选择，因树状数组原生仅支持前缀最值，最大值不可减、无法拆分，强行改造会导致复杂度上升、实现易错且不稳定。
线段树和树状数组都能做区间最大值查询（RMQ），但树状数组原生不支持区间最大值——它只天然支持前缀和、前缀最值（单点更新+前缀查询），强行改造成区间最大值会失效或退化。真要查任意 [l, r] 的最大值，线段树是更直接、可靠的选择。
为什么树状数组不能直接用于任意区间最大值查询
树状数组的结构决定了它只能高效维护“以 i 结尾的某类前缀信息”，比如 max(arr[1..i])。但 max(arr[l..r]) ≠ max(arr[1..r]) − max(arr[1..l−1])，最大值不可减，无法像求和那样拆分。有人尝试用两个树状数组（正向 + 反向）拼凑，但会导致：
- 查询复杂度升至
O(log²n)，且实现极易出错 - 单点更新时需同步维护多个依赖关系，边界 case（如
l == 1或r == n）容易漏判 - 在重复元素或平台差异（如 GCC vs Clang 优化）下行为不稳定
线段树实现 RMQ 的关键实操要点
标准线段树支持 O(log n) 查询与更新，代码清晰、可扩展性强。实战中要注意以下细节：
- 建树时使用闭区间
[l, r]更易对齐下标，避免mid计算溢出：用l + (r - l) / 2而非(l + r) / 2 -
query函数必须处理「查询区间完全落在左/右子树」和「横跨中点」三种情况，不能简单取左右结果的max后直接返回——未覆盖部分需忽略 - 若数组下标从
0开始，线段树节点仍建议按1-base 存储（即tree[1]为根），避免0下标导致位运算（如i ）误算 - 内存分配留足余量：大小为
4 * n是安全下限，别用2 * n—— 否则在某些n非 2 的幂时越界
示例片段（核心 query）：
立即学习“C++免费学习笔记（深入）”；
int query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return INT_MIN; // 无交集，返回极小值
if (ql <= l && r <= qr) return tree[node];
int mid = l + (r - l) / 2;
return max(query(node<<1, l, mid, ql, qr),
query(node<<1|1, mid+1, r, ql, qr));
}什么场景下可以考虑树状数组替代线段树
只有当查询模式受限时，树状数组才值得考虑——不是为了“更快”，而是为了“更省”或“更稳”：
- 只需查所有
[1, r]的最大值（前缀最大值），且更新只在末尾追加：用std::max_element+ 单调栈更轻量 - 静态数组（无更新）、离线查询：用 Sparse Table，
O(1)查询 +O(n log n)预处理，比线段树快且省空间 - 强制内存受限（如嵌入式），且查询仅限
[i, i+k]固定长度滑动窗口：用双端队列维护单调递减队列，O(1)均摊
线段树写一次能跑十年，树状数组改来改去容易翻车——尤其当需求悄悄从“前缀最大值”变成“任意区间最大值”时，那个被注释掉的 // TODO: support arbitrary range 很可能再没人敢动。
