分块优化算法通过将数组划分为大小为⌊√n⌋的块，预处理块内最大值，使区间最大值查询达到O(√n)时间复杂度和O(√n)空间复杂度，兼顾高频查询与内存受限场景。
如果您需要在大规模静态数组上执行高频区间最大值查询，且内存受限无法使用ST表，分块优化算法可提供平衡的时空性能。以下是实现该算法并解析其查询复杂度的具体步骤：
一、分块预处理：构建块内最大值数组
将长度为n的原数组划分为若干大小为B的连续块（最后一块可不足B），对每一块单独计算并存储其内部最大值，形成长度为⌈n/B⌉的块最大值数组。该步骤确保后续查询时能快速跳过完整块，仅需处理边界零碎区间。
1、设定块长B = ⌊√n⌋，避免块数与块长失衡导致最坏查询退化。
2、遍历原数组下标i从0到n−1，计算当前元素所属块编号block_id = i / B（整除）。
立即学习“C++免费学习笔记（深入）
”；
3、对每个block_id，维护临时变量max_in_block，每次遇到新元素即执行max_in_block = max(max_in_block, a[i])。
4、在每块结束位置（即i % B == B−1 或 i == n−1时），将max_in_block存入block_max[block_id]。
二、查询处理：三段式覆盖与合并
对任意查询区间[l, r]，将其拆解为左零散段、中间完整块段、右零散段三部分；左、右零散段直接线性扫描，中间块段通过查block_max数组获取各块最大值后取全局max。该策略保证查询时间严格受限于最多2B个元素扫描加最多⌈n/B⌉次数组访问。
1、计算左端点所在块left_block = l / B，右端点所在块right_block = r / B。
2、若left_block == right_block，说明[l, r]完全落在同一块内，直接遍历a[l]至a[r]求最大值。
3、否则，初始化ans = INT_MIN；先扫描左零散段：从l到min(r, (left_block + 1) * B − 1)，更新ans。
4、再扫描右零散段：从max(l, right_block * B)到r，更新ans。
5、最后遍历中间块编号从left_block + 1到right_block − 1，对每个i执行ans = max(ans, block_max[i])。
三、块长B的最优选择与查询复杂度推导
查询复杂度由零散段扫描代价O(B)与完整块访问代价O(n/B)共同决定；二者之和f(B) = B + n/B在B = √n时取得最小值，此时总查询时间为O(√n)，空间开销为O(√n)用于存储block_max数组。
C知道CSDN推出的一款AI技术问答工具下载
1、令B为正整数变量，写出查询最坏情况下的操作数上界表达式：
T(B) = 2B + ⌈n/B⌉。
2、忽略取整误差，视T(B) ≈ 2B + n/B，对其关于B求导得dT/dB = 2 − n/B²。
3、令导数为0，解得驻点B₀ = √(n/2)，代入后T(B₀) ≈ 2√(n/2) + n/√(n/2) = 2√(n/2) + √(2n) =2√(2n)。
4、实践中取B = ⌊√n⌋或B = ⌈√n⌉均可保证T(B) ≤3√n，满足O(√n)渐进界。
四、边界安全处理：防止越界与负数干扰
原始数组含负数时，初始ans不能设为0，否则将掩盖真实负最大值；同时块划分与索引计算必须严格使用闭区间语义，避免因整除截断或边界偏移导致遗漏元素。
1、声明ans变量时初始化为
INT_MIN，而非0或−1。
2、计算块起始下标用start = block_id * B，块终止下标用end = min(n − 1, (block_id + 1) * B − 1)。
3、在扫描零散段前，显式校验l ≤ r，若不成立则立即返回INT_MIN或抛出异常。
4、对block_max数组分配大小为
((n + B - 1) / B)，使用整数向上取整公式避免块数少算。
五、与ST表及线段树的复杂度对比验证
分块算法不依赖预处理倍增结构，无需O(n log n)时间建表，其O(n)预处理与O(√n)查询构成确定性上界；在n ≥ 1e7且q ≥ 1e5场景下，总操作量约为1e5 × 3×√1e7 ≈1e9，远低于线段树O(q log n) ≈ 1e5 × 24 = 2.4e6次操作但常数高3–5倍的实际耗时，也规避了ST表O(n log n) ≈ 1e7 × 24 = 2.4e8字节内存占用问题。
1、ST表空间复杂度为
O(n log n)，当n=1e7时约需280MB内存，而分块仅需O(√n)即约4KB。
2、线段树单次查询为
O(log n)，但实际指令数含多次分支预测失败与缓存未命中；分块访问局部性强，块内扫描连续，CPU预取效率更高。
3、在q次查询中，若q √n，分块的O(q√n)开始显现优势，拐点明确。