不能直接用std::max_element做RMQ查询，因其零预处理、纯暴力，单次O(n)，10⁵次查询易超时；RMQ核心是预处理换查询速度，分块法通过√n分块预存块最大值，查询仅扫两端残块+查中间整块，达O(√n)；ST表虽O(1)查询但需O(n log n)空间且不支持修改。
为什么不能直接用 std::max_element 做 RMQ 查询
每次查询都遍历区间，时间复杂度是 O(n)，10⁵ 次查询就可能超时。RMQ 的核心诉求是「预处理换查询速度」，而 std::max_element 零预处理、纯暴力，不满足高频查询场景。
分块索引（也叫“稀疏表 + 分块”混合思路）的关键在于：把数组切成大小为 B 的块，对每块预存最大值；查询时只扫两端不完整块 + 查中间整块的预存极值。
-
B通常取sqrt(n)，平衡预处理空间O(n/B)和单次查询最坏扫描量O(B) - 若强行追求理论
O(1)查询，需配合 ST 表（Sparse Table），但 ST 表空间是O(n log n)，且不支持修改 - 实际工程中，
B = 64或128往往比sqrt(n)更快——缓存友好，避免除法取块号
分块预处理怎么写才不出错
常见错误是块边界计算越界，或最大值数组索引错位。比如用 i / B 算块号没问题，但块内偏移写成 i % B 时，若数组长度不是 B 整数倍，最后一块的循环上限必须用 min(B, n - block_start) 控制。
推荐结构：用 vector<int> block_max</int> 存每块最大值，下标 k 对应第 k 块（从 0 开始），块范围是 [k * B, min((k+1) * B, n))。
立即学习“C++免费学习笔记（深入）”；
- 不要在预处理里反复调用
max_element—— 手写循环，边扫边更新当前块最大值，避免构造迭代器开销 - 初始化
block_max[k]时别用INT_MIN，改用块首元素，防止全负数数组出错 - 如果后续要支持单点修改，就额外维护每个块的
vector<int></int>或用deque维护单调队列——但那就不是纯分块了
RMQ 查询时两端残缺块怎么安全扫描
查询 [l, r] 时，真正要暴力扫的只有左残块（从 l 到本块末尾）和右残块（从下一块开头到 r），中间整块直接查 block_max。容易漏掉的是：当 l 和 r 在同一块内，此时没有整块可查，必须全程暴力。
判断逻辑建议写成：
int l_block = l / B, r_block = r / B;
if (l_block == r_block) {
// 全在一块内，暴力
} else {
int res = max(暴力扫[l, (l_block + 1) * B),
max(block_max[l_block + 1 ... r_block - 1]),
暴力扫[r_block * B, r + 1));
}
- 注意：
block_max下标是块号，范围是[l_block + 1, r_block - 1]，空区间时跳过 - 暴力扫描用普通 for 循环，别用
std::max叠加——分支预测友好，且避免函数调用压栈 - 如果编译器支持，给暴力循环加
[[likely]]（C++20）或手动展开前 2–4 个元素，对小残块有实测提升
真能 O(1) 吗？ST 表和分块的取舍点在哪
严格说，纯分块是 O(sqrt(n)) 查询，ST 表才是 O(1) 查询 + O(n log n) 预处理。但 ST 表的常数大、cache 不友好，且无法处理修改；而分块在 n ≤ 1e6、查询次数 ≤ 1e5 时，实测往往更快。
- ST 表的
st[i][j]表示从i开始、长度为2^j的区间的最大值，查询时拆成两个重叠区间：st[l][k]和st[r - (1，其中 <code>k = 31 - __builtin_clz(r - l + 1) - 分块更适合嵌入式或内存受限场景——空间仅
O(n / B)，B=128 时比 ST 表省 10 倍以上内存 - 如果数据静态且查询极多（如图形渲染中的视锥裁剪预计算），ST 表值得；否则优先分块，再考虑是否值得上线段树
最易被忽略的一点：分块的块大小 B 不是数学最优就最好，而是要贴合 CPU cache line（通常 64 字节）。int 是 4 字节，所以 B = 16（64 字节）或 32（128 字节）常比 sqrt(n) 实际更快——别迷信理论公式。
