分块RMQ无法达到O(1)查询，但可稳定实现O(√n)预处理与查询，兼顾效率、内存与实现简易性；块长应避免直接用std::sqrt(n)，以防浮点误差导致block_size*block_size≠n。
分块 RMQ 在 C++ 中无法做到 O(1) 查询，但能稳定压到 O(√n) 预处理 + O(√n) 查询，比朴素 O(n) 快，比线段树/ST 表更省内存、更易写；关键不是“快”，而是“够用且可控”。
怎么算块长？别信 sqrt(n)，直接取常数
用 std::sqrt(n) 算块长是高频翻车点：浮点误差可能导致 block_size * block_size ，最后一块漏覆盖；除法本身也有开销。实操中应设固定常量，比如 <code>BLOCK_SIZE = 384（2 的幂附近，cache line 对齐友好），或根据典型数据规模选 256 / 512。
- 若必须动态适配，改用整数上界：先设
block_size = 1，然后while (block_size * block_size ，避免浮点 - 块数计算别写
(n + block_size - 1) / block_size——除法慢，改用n / block_size + (n % block_size != 0) - 最后一块长度一定是
n - (block_cnt - 1) * block_size，不是block_size，所有遍历右边界必须用min()截断
query(l, r) 三段拆分必须严格覆盖，不能靠“大概”
常见错误是写成 if (l / B == r / B) { ... } else { 左残 + 中间块 + 右残 }，但漏掉中间块为空时的逻辑分支，或左右残段边界算错导致重复/遗漏。
- 左残段终点是
min(r, (l / B + 1) * B - 1)，不是(l / B + 1) * B - 1（否则越界） - 右残段起点是
max(l, (r / B) * B)，不是(r / B) * B（否则可能小于l） - 中间块范围是
[l / B + 1, r / B - 1]，循环前必须判断是否l / B + 1 ，空区间直接跳过 - 同块判断必须用整除结果比较：
lid = l / B; rid = r / B; if (lid == rid)，别在每次 query 里反复调sqrt()或做浮点运算
预处理 block_max 别用 std::max_element，手写循环+分支提示
套 std::vector<:vector>></:vector> 或调 std::max_element 会导致严重 cache miss 和分支预测失败，实测比手写慢 2–3 倍。
- 每块内用裸 for 循环扫描，起始位置
l = i * BLOCK_SIZE，结束位置r = std::min(l + BLOCK_SIZE, n) - 更新最大值用
if (a[j] > block_max[i]) [[likely]] block_max[i] = a[j];，避免函数调用和无谓分支 -
block_max必须单独连续分配（如std::vector<int> block_max(block_cnt)</int>），不能和left_max/right_max混在一个大 buffer 里——否则查中间块时 cache line 预取失效 - 如果后续要支持单点修改，只需重扫对应块：定位
bid = pos / BLOCK_SIZE，再跑一遍该块内循环，O(√n)完事
为什么不用 ST 表？缓存不友好才是真瓶颈
ST 表理论 O(1) 查询，但实际有硬伤：log n 层内存访问跨度大，局部性差；静态二维数组大小固定，难适配在线流式数据；而分块结构扁平，block_max 是一维连续数组，CPU 能一次预取多个块最大值。
- 当
n ≤ 1e6、查询频次中等、内存敏感（比如嵌入式或服务端低配实例），分块更稳 - 若需单点更新，分块改起来也简单：只更新对应块的
block_max[bid]，线段树得改懒标，ST 表根本不能改 - 真正容易被忽略的是：分块对原数组内存布局极度敏感——数组最好用
aligned_alloc(64, n * sizeof(int))分配，BLOCK_SIZE设为 64 字节倍数（如 16 个int），否则 cache line 利用率骤降
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
