分块优化RMQ算法通过预处理块最大值、左右单调栈数组实现O(√n)查询：先分块计算block_max，再构建left_max和right_max，查询时按单块、两块、多块三类合并结果。
如果您需要在C++中对静态数组进行多次区间最大值查询（RMQ），且要求单次查询时间尽可能低、预处理开销可控，则可采用分块优化策略替代线段树或ST表。以下是该分块优化算法的完整实现逻辑：
一、分块预处理：计算每块内部最大值
将长度为n的数组划分为若干大小为B的连续块（最后一块可不足B），对每一块单独遍历，预先计算并存储该块内的最大值，形成块最大值数组block_max。此步骤确保后续查询能快速定位块级上界。
1、设定块长B = ⌊√n⌋，初始化长度为⌈n/B⌉的block_max数组；
2、对每个块索引k（从0开始），计算起始位置L = k × B，结束位置R = min(L + B − 1, n − 1)；
立即学习“C++免费学习笔记（深入）”；
3、遍历区间[L, R]，逐元素比较并更新block_max[k]为该区间最大值；
4、完成所有块后，block_max[k]即表示第k块内所有元素的最大值。
二、边界处理：构建左右方向单调栈辅助数组
为高效处理查询区间跨块时的不完整左右端部分，需预处理两个辅助数组：left_max[i]表示从块首到位置i（含）的最大值，right_max[i]表示从位置i（含）到块尾的最大值。二者均按块内局部单调性构造，避免每次查询重复扫描。
1、对每个块k，设其左边界L = k × B，右边界R = min(L + B − 1, n − 1)；
2、正向遍历[L, R]，令left_max[L] = arr[L]，之后left_max[i] = max(left_max[i−1], arr[i])；
3、反向遍历[R, L]，令right_max[R] = arr[R]，之后right_max[i] = max(right_max[i+1], arr[i])；
4、所有块处理完毕后，left_max和right_max数组即具备块内任意前缀/后缀最大值快速查表能力。
三、查询执行：组合块内与块间信息
对于查询区间[l, r]，根据其覆盖范围分为三种情形：完全落在单一块内、跨越两块、跨越多块。统一采用“左残段 + 中间整块 + 右残段”三段式合并策略，利用预处理数组直接获取各段最大值并取全局最大。
1、计算l所在块id_l = l / B，r所在块id_r = r / B；
2、若id_l == id_r，说明[l, r]完全位于同一块，直接返回max(arr[l..r])，可用right_max[l]与left_max[r]交集或直接遍历（因B较小，耗时可接受）；
3、若id_l + 1 == id_r，说明仅跨两块：结果为max( right_max[l], left_max[r] )；
4、若id_r ≥ id_l + 2，说明存在中间整块：结果为max( right_max[l], max{ block_max[id_l+1] … block_max[id_r−1] }, left_max[r] )；
5、其中中间整块最大值可通过遍历block_max子数组获得，因块数最多为O(√n)，该步仍为O(√n)时间。
四、空间压缩：复用数组减少冗余存储
为降低内存占用，可将left_max与right_max合并为单一二维数组或利用原数组偏移地址隐式编码，同时block_max可复用arr末尾空闲空间（若动态分配）或使用vector.resize()精确控制容量。关键在于保证访问索引映射无歧义且不引发越界。
1、声明block_max为vector
2、申请left_max与right_max共用同一vector
3、对块k，left_max在aux中起始下标为k × B，right_max起始下标为k × B，但填充方向相反；
4、访问left_max[i]时直接取aux[i]，访问right_max[i]时也取aux[i]，因两者在各自块内已分别完成正向/反向递推，同一位置i在不同块上下文中含义不同，但不会冲突；
5、所有预处理完成后，aux数组同时承载两种方向的前缀/后缀极值信息。
五、边界校验：防止越界与空块误判
在实际编码中，必须对输入区间[l, r]做合法性检查，并对块索引及辅助数组访问加保护，尤其当n为0或B为0时需提前返回。所有数组访问前均需确认下标在有效范围内，否则会导致未定义行为。
1、若n == 0，直接返回0或抛出异常，不执行任何预处理；
2、若l r，立即返回一个标记值（如INT_MIN）或触发断言失败；
3、计算id_l与id_r后，强制约束id_l = max(0, min(id_l, num_blocks − 1))，id_r同理；
4、访问block_max[k]前判断k ∈ [0, num_blocks)，访问aux[i]前判断i ∈ [0, n)；
5、当某块为空（如B过大导致num_blocks=0），跳过该块相关逻辑，避免对空vector执行operator[]。
