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