分块RMQ在n≤5×10⁴、高查询低修改场景下更优，因其O(√n)查询常数极小：无递归、无指针跳转、缓存友好，实测比线段树快1.5–2倍；而线段树O(log n)理论优但分支预测失败和cache miss拖慢实际性能。
为什么分块 RMQ 比线段树更值得在小数据或离线场景中选
当数组长度
在 10⁴ 量级、查询次数
较高（比如 10⁵），且不支持修改时，分块 RMQ 的实际性能常优于线段树——不是因为渐进复杂度更优（它仍是
单次查询），而是因为常数极小：无递归调用、无指针跳转、缓存友好。线段树的
理论上更优，但每层都要取地址+比较+分支预测失败，实测在
时，分块常快 1.5–2 倍。
分块大小选
还是
？边界怎么处理才不出错
必须用
作为块长
，否则最后一块可能越界或漏覆盖。设
，块数为
（整除上取整）。常见错误是直接写
后强制
截断，导致
初始化预处理时，对每块
计算
，注意右端点用
保护，不能硬写
。
的三种情况必须拆开处理，不能合并逻辑
区间
跨块时，结果由三部分取最大值：
— 左侧散块（
到本块末尾）
— 中间完整块（查
数组）
— 右侧散块（本块开头到
）
若
和
在同一块内，直接遍历，别强行套三分逻辑。
立即学习
“
C++免费学习笔记（深入）
”；
C知道
CSDN推出的一款AI技术问答工具
下载
用
判断是否同块，比
更安全
左侧散块起始是
，终点是
；右侧散块起点是
，终点是
中间块范围是
，循环时注意左闭右闭，空区间要跳过
内存布局和 cache line 对性能的影响比算法本身还大
数组必须连续分配（如
或
），不能用
存块最大值——每次哈希查找成本远超遍历几十个数。更关键的是，块内数据在原数组中天然连续，CPU 预取能一次拉入整个 cache line（通常 64 字节 ≈ 16 个
），而线段树节点分散在堆上，cache miss 高发。
实测：把原数组改为
并确保
是 16 的倍数（如
），在密集查询下可再提速 10%–15%。但这只在
且 CPU L1d 缓存紧张时明显；小数据不必折腾对齐。
真正容易被忽略的是：分块法完全不支持单点更新。一旦有修改，要么重建全部
（
），要么退化成暴力——这时候该换 ST 表或线段树了。
nqO(√n)O(log n)n ≤ 5×10⁴⌊√n⌋⌈√n⌉⌈√n⌉BB = (int)ceil(sqrt(n))(n + B - 1) / BB = sqrt(n)intB*B ，最后几个元素无法被任何块覆盖。iblock_max[i] = max(arr[i*B], arr[i*B+1], ..., arr[min((i+1)*B-1, n-1)])min(i+1)*B-1query(l, r)[l, r]lblock_maxrlrl/B == r/Bl/B + 1 >= r/Blmin((l/B + 1) * B - 1, r)max(r/B * B, l)r[l/B + 1, r/B - 1]block_maxvectornew int[k]mapintaligned_alloc(64, n * sizeof(int))BB=128n > 10⁵block_maxO(B)