不能直接用 std::max_element 做 RMQ 查询，因其零预处理、纯暴力，时间复杂度 O(n) 每次查询，10⁵ 次易超时；RMQ 核心是预处理换查询加速，而它无法复用结果、不支持在线更新、隐含迭代器检查开销，且 vector 不提供 O(1) 区间极值。
为什么不能直接用 std::max_element 做 RMQ 查询
每次查询都扫一遍区间，时间复杂度是 O(n)，10⁵ 次查询就可能超时。RMQ 的核心诉求是「预处理换查询加速」，而 std::max_element 零预处理、纯暴力，完全背离目标。
常见误用场景包括：在循环里反复调用它查不同子区间，或误以为 vector 支持 O(1) 区间极值——实际上不支持。
- 它不保存任何结构信息，无法复用历史计算结果
- 迭代器范围检查开销隐性存在，高频调用下不可忽略
- 无法应对在线更新（哪怕只是理论限制）
分块索引怎么建才真 O(1) 查？关键在块内最值预处理
把数组每 B 个元素分成一块（建议取 B = 32 或 64，兼顾缓存行与计算量），对每块预先算出最大值，存进 block_max[] 数组。但仅这样还不够——跨块查询时，左右两端的「残缺块」必须快速响应。
真正实现 O(1) 的关键是：对每个块，额外预处理其「从块首到块内每个位置」的最大值（left_max[i]），以及「从块尾到块内每个位置」的最大值（right_max[i]）。这两个数组让任意块内子区间的极值变成查表操作。
-
B太小 → 块数多，block_max查询仍要O(√n)；太大 → 残缺块覆盖范围大，left_max/right_max预处理成本和内存飙升 - 不要用
vector存> left_max，按块平铺成一维数组更缓存友好 - 块编号用
i / B，块内偏移用i % B，避免除法指令（可位运算优化，如B=64时用i >> 6）
RMQ 查询函数怎么写？三段取 max 是唯一正确路径
给定 [l, r]，查询结果必然是三部分最大值：左残缺块（l 到块尾）、中间完整块（若干个 block_max）、右残缺块（块首到 r）。漏掉任一部分都会错。
示例代码逻辑骨架：
int rmq(int l, int r) {
int lid = l / B, rid = r / B;
if (lid == rid) {
return left_max[lid * B + r] - right_max[lid * B + l] + a[l]; // 实际需按定义调整
// 更稳妥：直接遍历 [l, r]，因块小，常数低
}
int res = max(right_max[lid * B + l], left_max[rid * B + r]);
for (int i = lid + 1; i
- 当
lid == rid（即l、r在同一块），别硬套公式，直接循环[l, r]—— 块大小固定且小，O(B) ≈ O(1) - 中间完整块循环必须用
for (int i = lid+1; i ，不是，否则重复计入边界块 -
right_max[i]定义为「从位置i到其所在块末尾的最大值」，left_max[i]是「从块开头到位置i」，二者方向相反，混用会返回错误值
为什么倍增 ST 表没在这里提？它和分块根本不是一档工具
ST 表预处理 O(n log n)、查询 O(1)，但不支持修改；分块预处理 O(n)、查询 O(√n)（严格说不是 O(1)，但工程中常称「类 O(1)」），却天然支持单点更新（改一个元素，只影响一个块的 block_max 和对应 left_max/right_max 片段）。
标题里写「O(1) 检索」是简化说法，实际指「查询耗时不随 n 增长，只取决于块大小」。真正需要理论 O(1) 且允许修改的场景，得上线段树或分块+堆——但那就不是本篇聚焦的轻量级方案了。
最容易被忽略的是：分块的「快」高度依赖 B 的选取和数据局部性。若数组随机访问模式差（比如 l、r 总落在不同块边缘），缓存失效频繁，实测可能比朴素扫描还慢。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
