分块RMQ因常数小、局部性好、预处理快，在静态小数据或离线场景中优于线段树；需静态数组，预处理三步：定块长⌊√n⌋、算块内最值、建块间ST表；查询时特判同块并拆分左右散块与中间整块，用ST表加速整块查询。
为什么分块 RMQ 比线段树更值得在小数据或离线场景中优先考虑
因为常数极小、内存局部性好、预处理快，且对 10^5 级别静态数组，分块的 O(n√n) 预处理 + O(√n) 查询实际跑得比线段树快不少——尤其当查询次数远少于修改次数（即几乎不修改）时。它不依赖递归、不建树、不 malloc 大量节点，适合嵌入式或缓存敏感环境。
关键前提：数组必须静态（初始化后不改）。一旦有单点更新，就得切回线段树或树状数组。
分块预处理三步走：分块大小、块内最值、块间稀疏表
核心是把数组切成 ⌊n / block_size⌋ 块，但块大小不能拍脑袋定。选 block_size = ⌊√n⌋ 是理论最优，平衡了块内扫描和块间跳转开销；实践中可微调为 64 或 128（适配 CPU cache line），但必须保证所有块（除最后一块）大小一致，否则边界逻辑爆炸。
- 第一步：为每块预计算块内最大值，存在数组
block_max[i]中，i是块索引 - 第二步：对
block_max数组建一个稀疏表（ST 表），支持O(1)块间区间最大值查询；注意 ST 表维度是num_blocks × log(num_blocks)，不是原数组尺寸 - 第三步：对每个位置
i，预存它所在块的起始下标block_start[i]和结束下标block_end[i]，避免每次算i / block_size * block_size引发除法开销
查询时如何合并「散块 + 整块」结果
查询 [L, R] 时，若跨块，必然拆成三段：左散块（L 到本块末）、中间整块（若干完整块）、右散块（下一块开头到 R）。但常见错误是直接暴力扫全部散块——其实只需扫最多两个散块（左+右），其余用 ST 表查整块最大值即可。
正确流程：
- 若
L和R在同一块，直接遍历[L, R]返回最大值（O(√n)上界，但均摊极小） - 否则，计算左块末位置
left_end = block_end[L]，右块初位置right_start = block_start[R] - 左散块：遍历
[L, left_end]；右散块：遍历[right_start, R] - 中间整块范围是
[left_end + 1, right_start - 1]，映射到块索引区间[left_block_id + 1, right_block_id - 1]，用 ST 表查最大值 - 取三者最大值返回
漏掉「同一块」特判会导致无谓建块区间、触发 ST 表越界；不缓存 block_start/block_end 会让每次查询多出 4 次除法和乘法。
容易被忽略的边界与性能陷阱
最隐蔽的问题是块大小取整方式：用 block_size = sqrt(n) 得到浮点数再强转 int，可能让最后一块过大或过小，导致 block_end[i] 超出数组边界。务必用 block_size = max(1, (int)floor(sqrt(n)))，并显式校验最后一块右端点 ≤ n-1。
另一个坑是 ST 表构建时的循环方向：必须外层枚举长度 j（从 1 开始倍增），内层枚举起点 i，否则 st[i][j] 依赖未计算的 st[i + (1，结果全错。
最后提醒：如果查询极少（比如只查 1–2 次），直接 O(n) 扫原数组反而更快——分块优化只为 amortize 查询成本，不是银弹。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
