线段树实现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错位。常见错误包括：
立即学习“C++免费学习笔记（深入）”；
-
mid计算写成(l + r) / 2导致整型溢出，应改用l + (r - l) / 2 - 查询时没判断当前节点区间与查询区间无交集，漏掉
if (r qr) return INT_MIN - 更新时只改叶子，忘了向上回溯调用
push_up（即tree[node] = max(tree[left], tree[right])）
一个最小可用片段：
void build(int node, int l, int r) {
if (l == r) { tree[node] = arr[l]; return; }
int mid = l + (r - l) / 2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
tree[node] = max(tree[node*2], tree[node*2+1]);
}
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*2, l, mid, ql, qr),
query(node*2+1, mid+1, r, ql, qr));
}
静态RMQ优先用Sparse Table，动态才选线段树
如果数组不更新，O(n log n)预处理 + O(1)查询的Sparse Table才是最优解，比线段树快一个数量级。线段树真正优势在于支持单点修改后的在线查询。树状数组在这里既不快也不简，还容易写错；除非你明确只要前缀最大值（如单调栈替代场景），否则别为“省那40%内存”强行用它做RMQ。
最易被忽略的一点：线段树数组大小必须开到4 * n，不是2 * n——因为最坏情况下叶子层有n个节点，但非完全二叉树会导致总节点数接近4n，开小了访问越界不报错但结果随机。
