分块 rmq 不适合高频单点更新，因单点修改需重算整块最值，最坏 o(√n) 重构，慢于线段树的 o(log n)；块大小取 ⌊√n⌋ 为控块数上界并防越界；查询分三段处理，仅残块扫描、整块查表；混用 st 表破坏其轻量优势。
为什么分块 RMQ 不适合高频单点更新场景
分块 RMQ 的核心优势在于静态或低频修改下的 O(1) 查询，但它不维护块内动态结构。一旦发生单点修改，必须重算整个块的最值——最坏情况触发 O(√n) 重构，比线段树的 O(log n) 还慢。如果你的业务中 update() 和 query() 频次接近，直接放弃分块，改用 std::vector + 线段树或 std::set 维护区间候选值更实际。
块大小取 ⌊√n⌋ 而非 ⌈√n⌉ 的真实影响
取 ⌊√n⌋ 是为了控制块数上界为 ⌈n / ⌊√n⌋⌉ ≤ √n + 1，确保预处理数组 block_max[] 大小可控。若误用 ⌈√n⌉，当 n = 99 时，⌈√99⌉ = 10，块数变成 10，但最后一块仅含 9 个元素，而预处理仍按满块逻辑写死长度，容易在循环中越界访问 arr[i * block_size + j]。实操中建议统一用：
int block_size = static_cast<int>(sqrt(n)); int block_cnt = (n + block_size - 1) / block_size;</int>
查询时跨块边界怎么避免重复扫描整个区间
分块 RMQ 查询分三段：左残块、中间整块、右残块。关键不是“跳过”，而是“只扫残块 + 查表整块”。中间整块直接查预处理好的 block_max[k] 数组，O(1)；左右残块各自最多扫 block_size − 1 个元素，合起来 O(√n)。常见错误是把左/右残块也拆成块查表，反而引入冗余判断。正确逻辑是：
- 若查询区间
[l, r]完全落在一个块内，暴力扫arr[l..r] - 否则，计算
l_block = l / block_size，r_block = r / block_size - 左残块：从
l扫到(l_block + 1) * block_size − 1 - 右残块：从
r_block * block_size扫到r - 中间块：对
k ∈ [l_block + 1, r_block − 1]取max(block_max[k])
预处理 block_max[] 和 st_table[][] 混用会破坏复杂度
有人想“增强”分块，在每个块内再建 ST 表，以为能降查询到 O(1)。但这样预处理空间变成 O(n log √n) = O(n log n)，且块内 ST 查询需 O(1) 但常数极大；更严重的是，它让代码失去分块本意——轻量、易调试、缓存友好。真正需要 O(1) 查询且可接受 O(n log n) 预处理的，直接用标准 ST 表即可，别硬套分块。分块 RMQ 的价值恰恰在于用 O(√n) 空间换简单性和局部性，这点容易被忽略。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
