分块适用于动态更新频繁、内存受限或区间不对齐场景，以O(√n)修改和查询平衡效率；预处理将数组分块并维护每块最大值，查询时暴力处理残缺块、查表处理完整块。
为什么不用线段树或 Sparse Table 而选分块
当数据动态更新频繁（比如单点修改）、内存受限，或查询区间不满足 2 的幂次对齐时，SparseTable 的 O(n log n) 预处理和只读限制就成硬伤；segment tree 虽支持修改，但常数大、缓存不友好。分块在「修改+查询混合」且 n 在 1e5 级别时，能用 O(√n) 查询 + O(√n) 修改平衡两者，实际跑得比理论更快。
分块预处理：每个块内维护最大值数组
把长度为 n 的数组 a[] 划分为 block_size = ⌊√n⌋ 大小的块（最后一块可不满）。对每块 i，预计算其内部最大值存入 block_max[i]。
注意三点：
- 块编号从
0开始，第i块覆盖下标[i * block_size, min((i+1) * block_size - 1, n-1)] - 不要用
ceil(sqrt(n))当block_size—— 容易导致块数 ≠⌈n / block_size⌉，后续越界 - 预处理复杂度是
O(n)，不是O(n√n)：每个元素只被扫一次
示例（n=10, block_size=3）：
立即学习“C++免费学习笔记（深入）”；
a[] = [2, 5, 1, 8, 3, 9, 4, 7, 6, 0] blocks = [[2,5,1], [8,3,9], [4,7,6], [0]] block_max = [5, 9, 7, 0]
RMQ 查询：暴力 + 块间查表的组合策略
查 [l, r] 区间最大值时，分三段处理：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 左残缺块：从
l到该块末尾，暴力扫 - 中间完整块：用
block_max[]直接取最大值（O(1) 每块） - 右残缺块：从该块开头到
r，暴力扫
关键细节：
- 块号用
l / block_size和r / block_size计算，整型除法自动向下取整 - 若
l和r在同一块内（即l / block_size == r / block_size），跳过中间块逻辑，全暴力 - 查询复杂度严格是
O(√n)：左右残缺部分各 ≤block_size，中间块数 ≤√n
代码片段核心逻辑：
int query(int l, int r) {
int res = INT_MIN;
int lb = l / block_size, rb = r / block_size;
if (lb == rb) {
for (int i = l; i <= r; ++i) res = max(res, a[i]);
} else {
for (int i = l; i < (lb + 1) * block_size; ++i) res = max(res, a[i]);
for (int i = lb + 1; i < rb; ++i) res = max(res, block_max[i]);
for (int i = rb * block_size; i <= r; ++i) res = max(res, a[i]);
}
return res;
}
单点修改如何保持 block_max 一致性
改 a[pos] = val 时，只影响它所属的那一个块：
- 先定位块号：
bid = pos / block_size - 直接更新
a[pos] = val - 重算整个块的最大值：
block_max[bid] = *max_element(a + bid * block_size, a + min((bid + 1) * block_size, n))
不要试图“增量更新” block_max —— 看似省事，但一旦块内最大值恰好是被修改的那个元素，你就得重新扫；而块大小仅 √n，重算开销稳定可控。实测中，这个“笨办法”比各种分支判断更快也更稳。
真正容易漏掉的是边界：当 n 不是 block_size 整数倍时，最后一块长度 ，<code>min((bid + 1) * block_size, n) 这个上界必须写对，否则越界读。
