分块算法是c++中rmq的实用选择：将数组划分为⌊√n⌋大小的块，预处理块内极值及块间前缀/后缀最大值，查询时合并左散块、整块、右散块三段结果，注意边界检查与整数除法。
要在C++中对静态数组实现大量区间最大值查询（RMQ），且单次查询必须严格控制在亚线性时间，又无法接受O(n log n)预处理空间的稀疏表（ST表），分块算法是兼顾预处理开销与查询速度的实用选择。
分块预处理：划分+块内极值+块间前缀/后缀最大值
将长度为n的数组a[]划分为⌊√n⌋大小的块（最后一块可不满），共B = ⌈n / ⌊√n⌋⌉块。
为每个块i（0 ≤ i
构建两个辅助数组：left_max[i]表示从块首到位置i的最大值，right_max[i]表示从位置i到块尾的最大值；二者均按块内顺序递推填充，每块耗时O(√n)，总预处理时间O(n)。
【块大小必须取floor(sqrt(n))而非ceil(sqrt(n))，否则块数可能超限导致right_max越界】
RMQ查询：覆盖三段——左残块→中间整块→右残块
给定查询区间[l, r]，设l所在块为L，r所在块为R：
① 若L == R：整个区间落在同一块内，直接返回max(a[l..r])，用预先计算的right_max[l]和left_max[r]组合可得，O(1)。
② 若L + 1
方法一：不额外建ST表 → 中间块遍历需O(√n)，总查询O(√n)。
方法二：对block_max数组再建稀疏表 → 预处理O(B log B) = O(√n log n)，但块数B ≈ √n，log B ≈ ½ log n，实际增长缓慢；查询中间块最大值降为O(1)，总查询退化为O(1)。
注意：方法二仅当查询频次远高于预处理开销时才值得引入，否则徒增常数。
代码核心结构与边界处理
定义全局变量：vector
预处理函数中先算block_sz = (int)sqrt(n)；再用for (int i = 0; i
查询函数入口立即判断l > r，直接返回INT_MIN——这步漏掉会导致未定义行为。
计算bid = i / block_sz时，务必使用整数除法，【禁止用double sqrt再round，浮点误差会使块边界错位】。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
