分块的引入
有一个长度为 $n$ 的序列 $a[1 \cdots n$，要求支持以下两种操作：
- 给下标在区间 $[l, r]$ 里的数加上 $d$；
- 查询下标在区间 $[l, r]$ 里的数的和。
链接：一个简单的整数问题2 或者 P3372 【模板】线段树 1
除了使用线段树/树状数组之外，还可以使用分块。
分块法
分块法，顾名思义就是把一个序列分成若干块。
假设把这个长度为 $n$ 的序列分成了 $m$ 块，每块的大小是 $n / m$。
对于区间加：观察 $[l, r]$ 这个区间。对于 $m$ 块，每一块维护的都是原序列中的 $[L[i], R[i]]$ 这个下标里的元素。
如果 $1 \leqslant L[i] \leqslant R[i] \leqslant r$，就说明这一块里的元素每个都被加上了 $d$，不需要对每个元素都去加，只需要给这个块打上一个标记，表示块内的元素每个都被加上了 $d$。
这一步复杂度是 $O(m)$。
如果 $[l, r]$ 没能覆盖 $[L[i], R[i]]$，但是仍然有交集，那只需要把交集的部分暴力 $+d$ 即可。最多可能要加 $n / m$ 次，所以复杂度是 $O(n / m)$。
对操作 $1$，时间复杂度是 $O(m + n / m)$。
对于操作 $2$，查询区间 $[l, r]$ 的和。
只需要对每一块维护一个和 $sum$，和一个标记 $tag$。
$tag$ 表示这个区间里每个元素都要被加的值。
那么一个完整的块的和就是 $sum + tag *$ 块长对于其他的不是覆盖但是有交集的元素，就是暴力求和。
这一步复杂度也是 $O(m + n / m)$。
因此单个操作的时间复杂度都是 $O(m + n / m)$
取 $m = \sqrt{n}$ 的时候，单个操作的时间复杂度就是 $\sqrt{n}$
这样时间复杂度就是 $q\sqrt{n}$，空间复杂度仍为 $O(n)$。
分块法的应用
有一个长度为 $n$ 的序列 $a[1 \cdots n]$，要求支持以下两种操作：
- 给下标在区间 $[l, r]$ 里的数加上 $d$；
- 查询区间 $[l, r]$ 中有几个数小于 $v$。
思路：
块内整体维护，落单的暴力维护。
