前言
近期也是把hzwer的数列分块入门肝完了，感觉分块很玄学（
什么是分块
分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。
分块的时间复杂度主要取决于分块的块长，一般可以通过均值不等式求出某个问题下的最优块长，以及相应的时间复杂度。
分块是一种很灵活的思想，相较于树状数组和线段树，分块的优点是通用性更好，可以维护很多树状数组和线段树无法维护的信息。
当然，分块的缺点是渐进意义的复杂度，相较于线段树和树状数组不够好。
不过在大多数问题上，分块仍然是解决这些问题的一个不错选择。
分块的巧妙之处在于对大块通过预处理后能够实现快速对区间信息进行修改，零散块暴力，大块整体修改，使得分块虽然看起来是暴力，但是时间复杂度是 \(O(n \sqrt\n)\) 的。
分块一般要维护的信息
我个人的习惯是维护每个块的头和尾，每个点所在块的编号，以及每个块的标记。
关于块长 \(len\) 一般是把它设为 \(\sqrt\n\) ，具体的数值应该根据题目的数据范围来定。
分块的预处理
定义 \(len\) 为每个块的长度，\(num\) 为块的数量，不难得到
int len = sqrt(n), num = n / len + (n % len ? 1 : 0);
for(int i = 1;i <= num;i ++)
t[i] = ed[i - 1] + 1, ed[i] = st[i] + len - 1;
for(int i = 1;i <= num;i ++)
for(int j = st[i];j <= ed[i];j ++)
pos[j] = i;
下面以LOJ的数列分块入门为例。
数列分块入门1
题意：区间加，单点查询。
很裸的题目，有各种方法做，我这里选择分块。
考虑对每个块维护一个标记 \(tag\) ，修改时遵循零散块暴力，大块
标签：暴力,分块,复杂度,len,优雅,sqrt,块长 From： https://www.cnblogs.com/Svemit/p/17255387.html