分块算法通过预处理每块最大值实现区间最值查询：先分块并计算各块最大值，查询时分别处理左右残缺段和中间整块，最后合并三者最大值得到结果。
如果您需要在静态数组上快速回答多个区间最大值查询，且希望避免线段树或ST表的预处理开销，分块算法提供了一种空间与时间均衡的实现方式。以下是该算法的核心逻辑与具体实现步骤：
一、分块预处理：计算每块内部最大值
将原数组划分为若干大小为 ⌊√n⌋ 的连续块，对每个块单独遍历，预先计算并存储该块内的最大值。此步骤确保后续查询时能以常数时间获取整块的极值信息。
1、设数组长度为 n，块大小 block_size = max(1, (int)floor(sqrt(n)))。
2、计算块总数 num_blocks = (n + block_size - 1) / block_size。
3、声明数组 block_max[num_blocks]，对每个块索引 i（0 ≤ i
二、边界处理：覆盖不完整块的暴力扫描
当查询区间 [L, R] 跨越多个块时，左右两端可能落在块内部而非块边界，此时无法直接复用 block_max；需对两端未被整块覆盖的部分进行线性扫描，确保不遗漏任何候选元素。
1、确定 L 所在块编号 left_block = L / block_size，R 所在块编号 right_block = R / block_size。
2、若 left_block == right_block，则整个区间位于同一块内，直接遍历 [L, R] 求最大值。
3、否则，初始化答案 ans 为 -∞，先遍历左端残缺部分 [L, (left_block + 1) × block_size - 1]，再遍历右端残缺部分 [right_block × block_size, R]，分别更新 ans。
三、整块跳过：利用预处理结果加速中间段查询
对于查询区间中完全被覆盖的中间块（即从 left_block + 1 到 right_block - 1 的所有块），可直接取对应 block_max 值参与比较，避免逐个访问原始数组元素，显著降低时间复杂度。
1、若 right_block - left_block > 1，则循环遍历块索引 k = left_block + 1 到 k = right_block - 1。
2、对每个 k，执行 ans = max(ans, block_max[k])。
四、合并结果：整合三部分最大值
最终查询结果由左残缺段、中间整块段、右残缺段三部分的最大值共同决定；必须将三者结果统一比较，才能保证全局正确性。
1、将左残缺段扫描所得最大值记为 left_max。
2、将右残缺段扫描所得最大值记为 right_max。
3、将中间整块段比较所得最大值记为 mid_max（若存在），否则 mid_max = -∞。
4、返回 max({left_max, right_max, mid_max})。
五、查询优化：提前终止与边界剪枝
在残缺段扫描过程中，若当前已知最大值大于等于该块理论最大值（即 block_max 对应块的值），且后续剩余元素均不可能超越该块最大值，则可跳过部分比较；但需注意仅适用于严格单调递减假设不成立的通用场景，此处采用保守策略：仅在已知当前 ans ≥ block_max[k] 且 k 为唯一待查整块时跳过该块——实际实现中通常省略此步以保正确性，但逻辑上允许条件判断插入。
1、在左残缺段扫描前，获取 left_block 对应的 block_max[left_block]。
2、若 left_block == right_block，且 block_max[left_block] 已知，则扫描 [L, R] 后无需额外比较。
3、在进入右残缺段前，检查是否已有 ans ≥ block_max[right_block]，若是，仍须完成扫描，因右残缺段元素可能大于 block_max[right_block]（block_max 是块内最大值，但右残缺段是其子集，其最大值 ≤ block_max[right_block]；因此若 ans ≥ block_max[right_block]，则右残缺段无需扫描——此为关键剪枝点：当 ans ≥ block_max[right_block] 时，跳过右残缺段遍历。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
