分块算法适用于静态数组的RMQ，通过√n分块预处理实现O(√n)查询与O(√n)空间：先划分大小为⌊√n⌋的块并预存块最大值；查询时拆解为左右残量遍历和中间整块查表；块大小动态取⌈√n⌉以平衡性能。
如果您需要在静态或低频更新的数组上实现区间最大值查询（RMQ），且线段树的 O(log n) 查询常数过高、ST 表内存超限（如 n 达 1e7），则分块算法是一种空间可控、实现简洁、缓存友好的替代方案。以下是该算法的核心逻辑与复杂度优化步骤：
一、分块预处理：将数组划分为大小为 ⌊√n⌋ 的块并维护块内最大值
分块法将原数组 a[0..n−1] 划分为若干连续块，每块长度设为 block_size = ⌊√n⌋（或取最接近的整数），最后一块可不满。对每个块 i，预先计算并存储其内部最大值，存入数组 block_max[i]。该预处理确保后续任意完整块的查询可在 O(1) 时间内完成，且总空间开销仅为 O(√n)，远低于 ST 表的 O(n log n) 或线段树的 O(4n)。
1、计算块大小：block_size = (int)sqrt(n)，若 n=0 则直接返回；
2、确定块总数：num_blocks = (n + block_size - 1) / block_size；
3、为 block_max 分配空间：vector
4、遍历原数组，对每个下标 pos，计算所属块号 bid = pos / block_size；
5、执行 block_max[bid] = max(block_max[bid], a[pos])；
二、单次 RMQ 查询：拆解为左残量、中完整块、右残量三段处理
对于查询区间 [l, r]，无法被整块覆盖的部分称为“残量”——即 l 所在块的右半部分与 r 所在块的左半部分；中间完全落入块内的部分可批量查 block_max。该策略避免逐元素扫描，将最坏查询时间控制在 O(√n)，且实际运行中因缓存局部性优于理论值。
1、若 l 与 r 属于同一块（即 l / block_size == r / block_size），则直接遍历 a[l] 到 a[r] 求最大值；
2、否则，初始化 ans = INT_MIN；
3、处理左残量：从 l 向右遍历至该块末尾（即 min(r, (l / block_size + 1) * block_size - 1)），更新 ans；
4、处理右残量：从 r 向左遍历至该块开头（即 max(l, (r / block_size) * block_size)），更新 ans；
5、处理中段完整块：遍历块号从 l/block_size + 1 到 r/block_size - 1，对每个块号 bid 取 block_max[bid] 并更新 ans；
三、块大小优化：采用 ⌈√n⌉ 而非固定 32 或 64 提升适应性
固定块大小（如 32）会导致在 n 较小时块数过多、残量过大，在 n 较大时块内遍历开销上升。动态取 ⌈√n⌉ 可平衡块数量与单块长度，使最坏查询复杂度严格维持在 O(√n)，且在不同规模数据下均保持稳定性能表现。
1、使用 int block_size = (int)ceil(sqrt((double)n)) 替代硬编码值；
2、注意 ceil(sqrt()) 在 n 为完全平方数时需防浮点误差，推荐写法：block_size = sqrt(n) + 1e-9; 后强制转 int 再校验；
3、若 block_size
4、重新计算 num_blocks = (n + block_size - 1) / block_size；
四、查询边界安全处理：防止残量遍历时下标越界
当 l 或 r 接近数组边界（如 l=0 或 r=n−1）时，残量遍历若未严格限定范围，易触发 a[pos] 越界访问。必须在每次访问前校验下标有效性，并将残量循环限制在 [l, r] 闭区间内，而非依赖块边界推导。
1、左残量起始为 l，结束为 min(r, (l / block_size + 1) * block_size - 1)；
2、右残量起始为 max(l, (r / block_size) * block_size)，结束为 r；
3、在循环体内加入 if (pos >= n || pos
4、所有数组访问必须前置下标检查，不可假设输入 l、r 合法；
五、支持单点更新的增量维护：仅重算对应块的最大值
分块结构天然支持 O(√n) 单点更新：修改 a[pos] 后，仅需重新扫描其所在块的全部元素，更新 block_max[bid]。相比线段树的 O(log n) 更新，其常数更低、代码更简，且无父子索引失效风险，特别适合更新频率低于查询频率两个数量级的混合场景。
1、计算块号 bid = pos / block_size；
2、重置 block_max[bid] = INT_MIN；
3、遍历该块起始下标 start = bid * block_size 至结束下标 end = min(n - 1, start + block_size - 1)；
4、对每个 idx ∈ [start, end]，执行 block_max[bid] = max(block_max[bid], a[idx])；
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
