分块适用于高查询低修改场景，因常数小、内存局部性好且支持简单更新；建块时取√n左右大小并预处理块最大值，查询分三段处理，单点修改仅更新对应块，易错点在边界计算与块内判断。
为什么不用线段树或 Sparse Table 而选分块？
当查询频次高、修改偶尔发生（比如静态数组上做大量 query(l, r)），且数据规模在 1e5 量级时，分块的常数和内存局部性往往比线段树更优；Sparse Table 虽然 O(1) 查询，但不支持修改，且预处理空间是 O(n log n)，而分块仅需 O(n) 额外空间。分块还天然支持区间赋值、加法等简单更新——只要块内维护得当。
分块结构怎么建？关键在块内最大值与跨块处理
把长度为 n 的数组划分为 block_size = sqrt(n) 大小的块（最后一块可不满）。对每块预处理其最大值，存入 block_max[] 数组。查询 [l, r] 时分三段处理：
- 左散块：暴力遍历
l到块尾 - 中间整块：查
block_max[i]的区间最大值（可用 ST 表或再分块，但通常直接遍历这些块，因为最多O(sqrt(n))块） - 右散块：暴力遍历块首到
r
注意：block_size 不必严格等于 sqrt(n)，取 300 或 512 等便于 cache 对齐的值反而更快；用 vector<int> block_max</int> 而非 int* 更安全，但需确保其 size 是 (n + block_size - 1) / block_size。
如何支持单点修改？只更新所在块即可
修改 a[pos] = val 时，只需定位到块编号 pos / block_size，然后对该块重新扫一遍计算新最大值。时间复杂度 O(block_size)，均摊下来仍远优于线段树的 O(log n) 常数开销。但要注意：
立即学习“C++免费学习笔记（深入）”；
- 别忘了同步更新原数组
a[pos]，否则后续暴力扫描会出错 - 如果块大小设为
1或过大（如n），就退化成暴力或线段树，失去分块意义 - 若需区间修改（如加一个数），则必须引入懒标记，此时建议改用线段树——分块懒标管理成本陡增
实际写的时候最容易错哪几个地方？
边界判断是高频翻车点。例如块编号计算写成 pos / block_size + 1，导致越界访问 block_max；或暴力扫描时用 却没保证 <code>r 在当前块内，造成重复/遗漏。还有两个隐蔽坑：
-
block_size用int sqrt_n = sqrt(n)可能因浮点误差变小，应写成int block_size = (int)sqrt(n) + 1或更稳妥地用while (block_size * block_size - 查询时若
l和r在同一块内，必须跳过中间整块逻辑，直接暴力——否则会漏算或重复算 - 初始化
block_max[i]时，循环范围写成[i * block_size, min((i+1)*block_size - 1, n-1)]，而不是[i * block_size, (i+1)*block_size)，后者可能越界
分块的优势不在理论最值，而在可控的实现复杂度与贴近硬件的访存模式。一旦块大小和边界写错，性能会断崖下跌，甚至不如纯暴力——这点比算法选择本身更值得花五分钟反复验证。
