数列分块 | Grimner

type

status

date

slug

summary

分块数组建立

确定块长。

大多数情况下都是取。

确定块的左右端点

块左端点为上一个块右端点，右端点即为当前块编号乘块长。

维护块内信息

比如所属区间和区间和等内容。

例如：对一个长度为n 的数列建立分块数组

对于块内处理

主要是“大段维护，小段朴素”

根据题目变化；

也有类似线段树的懒标记

所以分块也可以以线段树的方式理解

线段树是深度为的树形结构，分块就是深度为 2的树形结构：

时间复杂度

显然，对于零散块，最长不过，同样，整块的块数也不超过。

所以m 次操作的时间复杂度就是。

扩：分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找间的查找方法。

分块九讲

数列分块入门 1

省流：区间加，单点求值。

~~树状数组也可以解决这道题，但是要用分块。~~

显然，在建立分块数组后，区间加有两种情况

修改区间在同一块内

区间不在同一块内

而在最后单点查询时添加上“懒标记”即可

数列分块入门 4

省流：区间加，区间求和

~~类似线段树的操作~~

区间加参考例一，但是注意在零散块中要同时修改sum的值。

区间求和操作也可以参考区间加操作，分为两种情况

数列分块入门 2

省流：区间加，区间查询小于某个数的个数。

显然：

对于一个无序数组，查询小于某数的个数需要的复杂度是。

对于有序数组，则可以通过二分查找达到的复杂度。

在预处理时将每个块内的元素进行排序；

这样就可以通过二分较为快速的求出整块内的小于某数的个数。

对于零散块，仅有某些数会增加，因此顺序会发生改变。需要暴力修改，重新排序后再二分查找。

而对于整块，注意到，整块区间加时，并不会影响其中元素的相对顺序。所以只需要更新懒标即可。区间查询直接二分即可。

完整代码：

数列分块入门 3

省流：区间加，区间查询某数的前驱。

类比“分块 2”，对有序数组查询前驱较为简单。

因此本题的思路和“分块 2”基本无异，只是细节实现上存在不同。

数列分块入门 5

省流：区间开方，区间求和。

可能感觉这道题很熟悉，这个。

考虑开方这个操作的特点。。而 int 范围内的任何数，开方不到 10 次就会变成 1。

因此，如果一个块的数全是 1，开方时就可以直接跳过此块。虽然开始的时候，能跳过的块基本没有，但是随着操作次数的增加，全为 1 的块越来越多，跳过的也越来越多。

数列分块入门 6

省流：单点插入，单点查询。

通过 vector 可以很容易的得到当前块的元素个数，那么通过遍历每个块，就能用的复杂度找到要插入的位置（查询同理）。块中插入直接用 vector 自带的 insert 就好。对于整个 vector 的单点插入复杂度是的，但是如果有个 vector，复杂度就变成了。

数列分块入门 7

省流：区间乘法，区间加法，单点询问。

类似于线段树 2 ，使用两个懒标。注意优先级和取模。