线段树实现RMQ更直观高效，支持O(log n)的build、query、update；树状数组因max不可逆，仅能高效查询前缀最大值，区间[l,r]查询最坏O(log²n)，且更新维护复杂。
线段树做RMQ比树状数组更直接，但树状数组能省空间
区间最大值（RMQ）在C++中用线段树实现最直观：每个节点存对应区间的max，支持build、query、update三类操作，时间复杂度都是O(log n)。树状数组（Fenwick Tree）原生只支持前缀和，要支持区间最大值，得改造成“最大值树状数组”，但存在本质限制：它不支持任意区间[l, r]的max查询，只能查[1, r]或配合额外技巧查[l, r]，且单点更新后无法高效维护区间最大值——因为max不可减，没有类似求和的逆元。
树状数组实现区间最大值必须放弃标准结构
标准树状数组靠lowbit向上聚合，依赖运算可逆；而max(a,b)没有逆运算，所以不能照搬。常见“最大值树状数组”实际是用树状数组维护“以i结尾的某段最大值”，仅支持query_max(1, r)，查[l, r]时需遍历O(log n)个节点取max，最坏退化到O(log²n)。示例写法：
int query_max(int r) {
int ret = INT_MIN;
while (r > 0) {
ret = max(ret, tree[r]);
r -= lowbit(r);
}
return ret;
}
// 注意：这只能查[1,r]，查[l,r]得另写逻辑，比如从r往左跳区间再合并
容易踩的坑：tree[i]含义不是“i管辖区间的最大值”，而是“从i - lowbit(i) + 1到i这段的最大值”——这个定义让合并变得别扭，且更新时需向所有父节点传播max，但父节点可能被多个子区间影响，无法保证一次更新到位。
线段树建树和查询代码简洁，边界处理决定成败
线段树实现RMQ的关键不在算法思想，而在下标管理和递归终止条件。推荐用闭区间[l, r]建树，根节点对应[0, n-1]（0-indexed），避免+1/-1错位。常见错误包括：
-
mid计算写成(l + r) / 2导致整型溢出，应改用l + (r - l) / 2 - 查询时没判断当前节点区间与查询区间无交集，漏掉
if (r qr) return INT_MIN - 更新时只改叶子，忘了向上回溯调用
push_up（即tree[node] = max(tree[left], tree[right])）
一个最小可用片段：
O(n log n)
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
