分块: 优雅的暴力算法

分块这么名字, 听起来十分的高大上 并没有 , 但是实际 板子 理解起来不是很难.

对于一个需要维护某种区间上的信息的序列, 我们可以将其拆分为几个子区间, 也就是块 . 这样, 对于每一个块, 我们可以分别维护块中的某一个值, 在查询区间中的该值时, 只需要将区间落到块上, 进行求解, 就可以大大缩小复杂度.

相较于线段树( \(O(\log_2n)\) ), 分块本身的复杂度是比较高(\(O(\sqrt n)\))的.

但是, 分块( 相对线段树 )有如下优点:

• 代码相对短小好写
• 易调试
• 常数小

在考试时, 分块也是一种得 骗 分的好办法.

分块的具体操作

以 P3372 线段树1 为例.

首先, 我们将整个范围分成若干一定大小的块.

• 关于块的大小问题, 一般将长度为 \(n\) 的序列分为大小为 \(\sqrt n\) 的若干块, 这样的时间复杂度较为稳定.
• 若 \(n\) 不是完全平方数, 便会生成出一个较小的块, 这个块叫做角块.

然后我们对于每个块像线段树的区间一样进行预处理, 处理出每个块的总和.

接下来进行操作, 对于每次操作( 无论是修改还是查询 )的区间 \(\left[l,r\right]\) , 都有如下的几种情况:

1. \(l\), \(r\) 在同一个块中:

   ? 此时我们无法利用分块的性质, 但因为范围不大( 最大\(\sqrt n\) ), 所以我们可以放心的直接操作.

   2. \(l\), \(r\) 在相邻的两个块中:

   ? 法同 1.

   3. \(l\), \(r\) 在不相邻的块中:

   ? 这时, 对于两边的块( \(l\), \(r\) 两端点所在的块 ), 我们仍然直接处理, 但是中间的完整的块, 我们就可以直接利用之前维护的值来更新了.

• 说明一下区间修改: 我们对每个区间维护一个标记, 需要修改时直接修改标记, 这样最后输出答案时处理一下标记即可.

总复杂度: \(O(\sqrt n)\).

附:实际上, 分块是一个 "原序列 -- 块 -- 值" 三层的树形结构.

[模板][数据结构] 分块

原文：https://www.cnblogs.com/Foggy-Forest/p/13267943.html