因查询极频繁、修改极少且n≈1e5时，分块常数更小、缓存友好；预处理用block_max、left_max、right_max三数组，块大小取√n并防0，左右端点需min/max校验，散块查询靠left_max与right_max加速。
为什么不用线段树而选分块做 RMQ？
当查询频次极高、修改极少（甚至无修改），且数据规模在 1e5 级别时，分块的常数远小于线段树，预处理 + 查询总耗时更稳。线段树单次查询是 O(log n)，但分支预测失败多、缓存不友好；分块把数组切成 √n 块后，块内最大值可预存在数组里，跨块查询最多扫两头 + 查一块——实际运行往往比理论更快。
注意：分块不支持区间修改（除非加懒标记，那就退化成带权分块，复杂度和实现难度飙升），所以确认是静态数组再用。
分块预处理怎么写才不出错？
核心是三个数组：block_max[i] 存第 i 块的最大值，left_max[i] 存从块左端点到位置 i 的最大值，right_max[i] 存从位置 i 到块右端点的最大值。后者两个用于处理“散块”（即查询区间两端不在同一块内时，左右残缺部分的快速极值）。
-
block_size = max(1, (int)sqrt(n))，必须取整且防n=0 - 块编号用
i / block_size，但右端点要算对：block_right[b] = min((b+1)*block_size - 1, n-1) - 填
left_max必须从每块左端点开始向右递推：left_max[l] = a[l]; for(int i=l+1; i - 填
right_max同理，从右往左；漏掉这一步，查跨块时会直接返回错误值
RMQ 查询逻辑怎么覆盖所有情况？
查询 [L, R] 时，只有一种情况能直接用 block_max：L 和 R 在同一块内，此时暴力扫 [L,R] 即可（长度 ≤ √n，均摊开销小）。其余情况拆三段：[L, block_end]（左残）、[block_start, block_end]（中间整块）、[block_start, R]（右残）。关键判断是块号：l_block = L / block_size, r_block = R / block_size。
- 若
l_block == r_block：直接循环求max(a[L..R]) - 否则：结果 =
max({right_max[L], block_max[l_block+1], ..., block_max[r_block-1], left_max[R]}) - 中间整块部分用循环查
block_max，不要手写公式跳过——边界易错，不如老老实实for(int b = l_block+1; b
时间复杂度和实际性能陷阱在哪？
预处理是 O(n)，每次查询最坏 O(√n)（全散块时扫两头 + 最多 √n 个块），但平均远低于此。真正卡性能的不是理论，而是内存访问模式：
-
block_max数组很小（约√n项），通常能进 L1 缓存；但若block_size取得不好（比如用sqrt(n)+0.5强制四舍五入），导致块数非整除，block_max长度波动，可能破坏缓存局部性 - 避免在查询中反复计算块号：
int l_block = L / block_size提前算好，别在循环里重复除法 - 如果数据是
vector<int></int>且反复查询，确保用.data()获取裸指针，减少边界检查开销
块大小不是越小越好——太小则 block_max 太长，整块查询次数上升；太大则残块扫描变慢。实测 block_size = 512 或 1024 在 1e5 数据上通常比理论 √n 更快。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
