采用分块+块内left_max/right_max+块间st表的混合结构，预处理o(√n)，查询严格o(1)：将数组分⌊√n⌋长的块，每块预存左右方向前缀/后缀最大值数组，并以块最大值构建st表实现块间快速rmq。
要在C++中对静态数组实现大量区间最大值查询（RMQ），且每次查询必须严格O(1)完成，不能接受线段树的O(log n)或ST表的O(1)但O(n log n)预处理开销，需采用分块索引优化策略——将数组划分为若干块，每块内预计算单调信息，块间用稀疏表加速，最终达成O(√n)预处理 + O(1)单次查询。
预处理：划分块并构建块内单调栈
设数组长度为n，取块长B = ⌊√n⌋，共⌈n/B⌉个块。对每个块i，从左到右扫描，维护一个单调递减栈，记录位置和值；同时为每个位置j预存“从块左端点到j的最大值”left_max[i][j−L_i]，其中L_i是块i的左边界索引。
这一步不能跳过块内left_max数组——若只存块整体最大值，跨块查询时无法快速获取左半段最大值。
对每个块i，再从右到左扫描，同样构建right_max[i][R_i−j]，即从位置j到块右端点的最大值。
构建块间稀疏表（Sparse Table）
方法一：以块为单位建ST表
将每个块i的全局最大值max_in_block[i]提取出来，构成长度为M = ⌈n/B⌉的一维数组。在此数组上构建标准ST表：st[k][i]表示从块i开始连续2^k个块中的最大max_in_block值。
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
st表维度为[log₂M + 1][M]，初始化st[0][i] = max_in_block[i]；递推式st[k][i] = max(st[k−1][i], st[k−1][i + 2^(k−1)])，仅当i + 2^(k−1)
【i + 2^(k−1) ≥ M时必须跳过，否则越界访问未初始化内存】
单次RMQ查询：三段合并法
给定查询区间[l, r]，执行以下步骤：
第一步：确定l和r所属块号，记为bl = l / B，br = r / B（整除）。
第二步：若bl == br，即l、r在同一块内，直接返回max(left_max[bl][r − L_bl], right_max[bl][L_bl − l])——注意此处要用块内偏移而非原始下标。
第三步：若bl ① 左残段：l到块bl右端点（含），查right_max[bl][L_bl − l]；
② 右残段：块br左端点（含）到r，查left_max[br][r − L_br]；
③ 中间完整块：从块bl+1到块br−1，用ST表查最大值——令len = br − bl − 1，k = floor(log₂(len))，结果为max(right_max[bl][L_bl − l], left_max[br][r − L_br], max(st[k][bl+1], st[k][br−1−(1
这一步必须严格按三段顺序合并，中间块若漏掉st[k][br−1−(1
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
