分块算法是C++中静态数组RMQ的高效方案：先按⌊√n⌋分块并预处理块最大值、前后缀极值，再分类查询，最后通过一维压缩和2的幂块长优化性能。
如果您需要在C++中对静态数组执行大量区间最大值查询（RMQ），且要求单次查询时间尽可能低、预处理开销可控，则分块算法是一种兼顾实现简洁性与实际性能的可行方案。以下是该算法的高效实现步骤：
一、分块预处理：将数组划分为大小为 ⌊√n⌋ 的块并维护块内最大值
将原数组按固定块长 B = ⌊√n⌋ 划分为若干块，对每一块单独计算并存储其内部最大值。该步骤使后续跨块查询可快速定位块级极值，避免逐元素扫描。
1、计算块长 B = static_cast
2、确定块数量 block_cnt = (n + B - 1) / B;
3、声明数组 block_max(block_cnt, INT_MIN);
4、遍历原数组下标 i = 0 到 n-1，计算所属块号 bid = i / B，更新 block_max[bid] = std::max(block_max[bid], arr[i]);
二、构建块间前缀/后缀最大值数组以支持不完整块快速合并
当查询区间跨越多个块且左右端点不在块边界时，需分别处理左残段、中间整块、右残段。为加速残段极值获取，预先为每块计算从块首到各位置的后缀最大值（suffix_max）和从块尾到各位置的前缀最大值（prefix_max）。
1、声明二维向量 suffix_max(block_cnt, std::vector
2、对每个块 bid，从块内最大下标开始倒序遍历：pos = std::min((bid + 1) * B - 1, n - 1) 到 bid * B，设 val = arr[pos]，suffix_max[bid][pos - bid * B] = std::max(val, (pos == std::min((bid + 1) * B - 1, n - 1)) ? val : suffix_max[bid][pos - bid * B + 1]);
3、声明二维向量 prefix_max(block_cnt, std::vector
4、对每个块 bid，从块内最小下标开始正序遍历：pos = bid * B 到 std::min((bid + 1) * B - 1, n - 1)，设 val = arr[pos]，prefix_max[bid][pos - bid * B] = std::max(val, (pos == bid * B) ? val : prefix_max[bid][pos - bid * B - 1]);
三、查询实现：分类处理区间覆盖形态并组合极值
根据查询区间 [L, R] 所跨块数，分三种情形处理：单块内查询、相邻两块部分覆盖、多块跨越。每种情形均利用已预处理的块内极值或前后缀数组，确保查询过程仅访问 O(√n) 个元素。
1、计算 L 所属块 l_block = L / B，R 所属块 r_block = R / B；
2、若 l_block == r_block，则结果为 suffix_max[l_block][L - l_block * B] 与 prefix_max[l_block][R - l_block * B] 的较大者；
3、若 r_block == l_block + 1，则取三者最大值：suffix_max[l_block][L - l_block * B]、block_max[l_block + 1]、prefix_max[r_block][R - r_block * B]；
4、若 r_block > l_block + 1，则取四者最大值：suffix_max[l_block][L - l_block * B]、block_max[l_block + 1]、block_max[r_block - 1]、prefix_max[r_block][R - r_block * B]；
四、空间压缩优化：使用一维数组替代二维 vector 存储前后缀信息
为降低内存分配开销与缓存不友好性，将 suffix_max 和 prefix_max 合并为两个一维数组，通过线性索引公式 bid * B + offset 映射二维逻辑位置，从而提升数据局部性与访问速度。
1、声明数组 suffix_flat(n, INT_MIN)，prefix_flat(n, INT_MIN)；
2、遍历每个块 bid，对块内偏移 off = 0 到块实际长度 - 1，计算物理下标 idx = bid * B + off；
3、将 suffix_max[bid][off] 值写入 suffix_flat[idx]，将 prefix_max[bid][off] 值写入 prefix_flat[idx]；
4、查询时，用相同公式还原逻辑块号与偏移，直接读取对应一维位置值；
五、边界对齐优化：强制块长为 2 的幂以启用位运算加速除法与取模
当数组长度允许时，将块长 B 设为不大于 √n 的最大 2 的幂（如 128、256），可将整除与取模操作替换为位移与位与，显著减少指令周期消耗，尤其在高频查询场景下效果明显。
1、计算 base = static_cast
2、设 B = 1; while (B
3、此时 l_block = L >> log2_B，其中 log2_B 为 B 对应的位移位数；
4、L 在块内偏移为 L & (B - 1)，无需调用 % 运算符；
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
