唯一可行解是分块索引优化：块大小取 max(1, ⌊log₂n⌋)，块数为 ⌈n/block_size⌉，预处理每块前后缀最大值表，实现O(1)查询与亚线性预处理。

要在C++中对静态数组实现大量区间最大值查询（RMQ），且每次查询必须严格 O(1) 时间完成，不能接受线段树的 O(log n) 或稀疏表的 O(1) 但 O(n log n) 预处理开销，就必须采用分块索引优化：将数组划分为大小为 ⌊log₂n⌋ 的块，预处理块内最值与块间ST表，再用块内位运算快速定位——这是唯一能兼顾常数级查询与亚线性预处理的工程解法。

分块大小与块数计算

取块大小 【block_size = max(1, (int)floor(log2(n)))】，其中 n 是数组长度；块数 blocks = (n + block_size - 1) / block_size。注意：block_size 不能为 0，n=1 时 log2(1)=0，必须兜底为 1。

计算 blocks 后立即声明 vector> block_max(blocks, vector(block_size, INT_MIN))，用于后续填入每块内部各前缀/后缀最大值。

构建块内前后缀最大值表

遍历每个块 i（0 ≤ i

立即学习“C++免费学习笔记（深入）”；

① 取该块起始下标 left = i * block_size，右边界 right = min(left + block_size, n)；

② 正向扫描：block_max[i][0] = arr[left]，对 j 从 1 到 right−left−1，执行 block_max[i][j] = max(block_max[i][j−1], arr[left+j])；

③ 反向扫描：令 block_max_rev[i] 为独立 vector，长度同块，设 block_max_rev[i][right−left−1] = arr[right−1]，再从倒数第二位向前递推，确保每个位置存的是「从该位置到块末尾」的最大值。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

构建块间稀疏表（Sparse Table）

提取每块整体最大值：vector block_overall(blocks)；对每块 i，block_overall[i] = block_max[i].back()；

基于 block_overall 构建 ST 表 st[k][i]，其中 k 为 2ᵏ ≤ blocks 的最大幂次，st[0][i] = block_overall[i]；

递推填充：for k from 1 to K−1 → for i from 0 to blocks − (1

O(1) 区间查询实现

方法一：完整覆盖于单一块内

若查询区间 [l, r] 完全落在同一块中（即 l/block_size == r/block_size），直接查 block_max 和 block_max_rev：返回 max(block_max[l/block_size][r−l], block_max_rev[l/block_size][r−l]) —— 注意此处索引偏移需按块内相对位置重算。

方法二：跨块查询

设 bl = l/block_size, br = r/block_size；若 bl+1

这一步必须用内置位运算 __builtin_clz 快速求最高位，手写循环求 log 会破坏 O(1) 性质。