基本思想
考虑一些在序列上的区间操作，如区间加和区间求和。
直接暴力做单次操作复杂度是 $\Theta(n)$，总时间复杂度 $\Theta(qn)$.
如果将序列分成 $\sqrt{n}$ 块，每块长度为 $\sqrt{n}$，并且对每个块维护里面所有元素的和，即可在 $\Theta(\sqrt{n})$ 的复杂度内进行单次操作。
具体实现如下：
-
令块的数量为 $num=\sqrt{n}$，单个块的长度为 $siz=\lceil\frac{n}{num}\rceil$.
-
记 $bel_i$ 表示 $i$ 号节点属于第几个块。
-
可以记录一些题目需要用到的信息，如 $sum_i$ 表示第 $i$ 个块内所有元素的和。
数列分块入门 9 题
T1 区间修改, 单点查询
对每个块维护整块加的值，查询的时候加上即可。
时间复杂度 $\Theta(n\sqrt{n})$。
T2 区间修改, 查区间内小于某个数的个数
对每个块内的元素排序，区间修改时整块大小顺序不变，散块暴力排序，查询时二分即可。
时间复杂度 $\Theta(n\sqrt{n}\log n)$。
排序使用归并可以将复杂度优化到 $\Theta(n\sqrt{n\log n})$。
T3 区间修改, 区间查前驱
同样是排序后在块内二分，只不过是把求比他小的数的数量改成求比它小的数中最大的那个。
时间复杂度 $\Theta(n\sqrt{n}\log n)$。
排序使用归并可以将复杂度优化到 $\Theta(n\sqrt{n\log n})$。
T4 区间修改, 区间求和
维护每个块的和以及加的数，用类似 $\rm T1$ 的方法维护。
时间复杂度 $\Theta(n\sqrt{n})$。
T5 区间开方, 区间求和
我们发现开方操作是没办法全局维护的，于是考虑寻找开方操作的性质。
观察到每个数被开方很少的次数以后就会变成 $1$（或者它本身就是 $0$，但这部分显然没有贡献，可以直接删去），于是对每个块记录一下里面 $1$ 的个数，如果全都是 $1$，就不对它进行开方，否暴力开方即可。
求区间和还是维护一下每个块的和。
时间复杂度 $\Theta(n\sqrt{n})$。
T6 单点插入, 单点查询
我们发现暴力做的时候需要将所有数向后移一位，单次时间复杂度 $\Theta(n)$。
于是考虑分块，给每个块预留 $\sqrt{n}$ 的剩余空间用来后移，记一下当前块的长度即可。查询的时候每访问一个块就把查询编号减去当前块的长度。不难发现这样做单次操作时间复杂度 $\Theta(\sqrt{n}).$
但是我们发现一个问题，如果插入全在一个块内的话复杂度很快就会变成 $\Theta(n)$，于是考虑每进行插入操作 $\sqrt{n}$ 次就重构分块即可。
时间复杂度 $\Theta(n\sqrt{n})$。
T7 区间修改(包含加和乘), 单点查询
考虑对每个块记 $\rm add$ 和 $\rm mul$，表示块内元素的真实值为 $a\times \rm mul+add$，区间加的时候，给 $\rm add$ 加上 $k$ 即可，区间乘的时候，不仅需要给 $\rm mul$ 乘上 $k$，还需要给 $\rm add$ 乘上 $k.$
时间复杂度 $\Theta(n\sqrt{n})$。
T8 区间查询数的个数并全部修改成这个数
我们发现如果询问区间小的话查询和修改都很容易，如果询问区间大的话会把很长一段都变成相同的数。如果记录一个块是否都是同一个数的话就很容易维护了。
不难发现这样做复杂度是 $\Theta(n\sqrt{n})$ 的。
T9 询问区间最小众数
记 $s_{i,j}$ 表示前 $i$ 个块中 $j$ 出现的次数，$p_{i,j}$ 表示第 $i$ 个块到第 $j$ 个块的众数。
我们发现，对于一次询问，答案一定是整块的众数或散块的众数，这个只需要对比一下即可。
时间复杂度 $\Theta(n\sqrt{n})$。
经典例题
[TJOI2009] 开关
记 $c_i$ 表示第 $i$ 盏灯是否开着，$sum_i$ 表示第 $i$ 个块中有多少盏灯开着，$d_i$ 表示第 $i$ 个块的状态是否整体改变。
对于区间取反操作，零散操作直接修改 $c_i$，并根据 $c_i$ 和 $d_i$ 决定 $sum_i+1$ 或 $-1$. 整块操作不用改变 $c$，直接令 $sum_i=R_i-L_i+1-sum_i$，并且将 $d_i$ 取反。
对于区间求和操作，零散点求和直接加上 $c_i\oplus d_i$，整块求和则加上 $sum_i$。
单次操作复杂度 $\Theta(\sqrt{n})$，总时间复杂度 $\Theta(q\sqrt{n})$。
[LG3396] 哈希冲突
转化题意，设计一种数据结构，支持：
考虑根号分治。
对于 $d\geqslant \sqrt{n}$ 的询问，直接暴力查询。
对于 $d \leqslant \sqrt{n}$ 的询问，记 $sum_{i,j}$ 表示从 $i(i\leqslant \sqrt{n})$ 开始，步长为 $j(j\leqslant \sqrt{n})$ 的答案。预处理的时候直接枚举计算即可，时间复杂度 $\Theta(n\sqrt{n})$。
对于修改操作 $a[pos]\leftarrow x$，先直接在原数列上进行修改，再考虑其对 $sum$ 数组造成了什么影响。易知，对于步长为 $d$ 的预处理数组，只会对 $sum_{pos\%d,d}$ 造成影响，于是对每个 $d(d\leqslant \sqrt{n})$ 修改一下即可，单次修改时间复杂度 $\Theta(\sqrt{n})$。
总时间复杂度 $\Theta[(n+q)\sqrt{n}]$。
[LG2801] 教主的魔法
考虑分块。
记原数列为 $A$，将 $A$ 复制一份记为 $B$，将 $B$ 分块，块内排序。
对于修改操作，整块直接打标记，散点修改完后再块内排序，这样完成操作后仍能保持分块数列的性质，单次操作复杂度 $\Theta(\sqrt{n}\log\sqrt{n})$。
对于查询操作，二分查找第 $i$ 个块内有多少个元素不小于 $k-add_i$，单次操作复杂度 $\Theta(\sqrt{n}\log \sqrt{n})$。
总时间复杂度 $\Theta[(n+q\sqrt{n})\log n]$。
考虑再对复杂度做一些优化，令块的大小为 $s$，则修改操作若采用归并排序，单次操作复杂度为 $\Theta(s+\frac{n}{s})$，同时单次查询复杂度为 $\Theta(s+\frac{n}{s}\log s)$。当询问次数为 $q$ 时，总复杂度为 $\Theta[q(s+\frac{n}{s}\log n)]\geqslant \Theta(q\sqrt{n\log n})$，取最小值当且仅当 $s=\sqrt{n\log n}$。
[国家集训队] 排队
分块 $+$ 树状数组。
考虑交换两个数 $a_u$ 和 $a_v$ 的贡献：
-
显然 $u$ 左边的数和 $v$ 右边的数没有贡献。
-
对于 $a_u$ 来说，贡献为 $u$ 到 $v$ 之间比它大的数的数量减去比它小的数的数量。
-
对于 $a_v$ 来说，贡献为 $u$ 到 $v$ 之间比它小的数的数量减去比它大的数的数量。
至于如何计算 $u$ 到 $v$ 之间比某个数大或小的值的数量，分块后散块直接暴力，整块建两颗树状数组即可。
令块大小为 $siz$，则时间复杂度为 $\Theta[nlogn+q(siz+\frac{n}{siz}logn)]\geqslant nlogn+q\sqrt{nlogn}$，取最小值当且仅当 $siz=\sqrt{nlogn}$，此时块的数量 $num=\sqrt{\frac{n}{logn}}$。
[LG4168] Violet 蒲公英
考虑分块，记 $s_{i,j}$ 表示前 $i$ 个块中颜色为 $j$ 的数量，$p_{i,j}$ 表示第 $i$ 个块到第 $j$ 个块的众数。
对于一次询问，先求出整块中的众数、众数的出现次数和所有在零散块中出现了的颜色的数量。显然，如果零散块中出现的颜色没有一个比众数出现的次数多，那么要求的众数就是整块的众数，否则是出现次数最多的颜色。
时间复杂度 $\Theta(n\sqrt{m})$。此时块大小 $B=\frac{n}{\sqrt{m}}$。