如何对比线段树与树状数组在实现区间最大值RMQ查询中的性能差异？

本文共计1155个文字，预计阅读时间需要5分钟。

树状数组（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)，逻辑清晰、边界可控。