「洛谷日报第20期」浅谈基础根号算法——分块

a
作者：刘浩宇（寂）

https://www.luogu.org/blog/48265/qian-tan-ji-chu-gen-hao-suan-fa-fen-kuai

分块算法实质上是一种是通过分成多块后在每块上打标记以实现快速区间修改，区间查询的一种算法。其均摊时间复杂度为O(√n)

分块算法相较于各种树形数据结构，具有简便易写，方便调试等多种优点。在同等数据规模下，如1e5，其时间效率并不会低太多，在考试时反而是一种有力的得分方法。

接下来讲一下分块算法的基本操作及性质：

为了使得其有着最稳定的时间复杂度，我们经常讲一个长度为n的序列分为√n个大小为√n的块，如果n不是完全平方数，则序列最右端会多出一个角块

如下图，就是一种序列的分块：

该长度为10的序列被分为了4块，前三块的大小为√10的近似值3，最后一个角块大小为1

而我们要记录的一个值，就是每个序号代表的数，属于哪一块

如上图，1,2,3就属于第一块，4,5,6就属于第二块，7,8,9就属于第三块，10就属于第四块

可以得到获取每一个序号的所在块的代码是：

但是，如何用分块来维护区间最值？

我们举个例子:

给定一个长的为n数列，求出任意区间[l,r]的最大值(1<=l,r<=n)(l<=r)

可能你会说：我会线段树！

但是拿分块又怎么做呢？

还是拿这张图，我们现在给每个点上加了一个权值，每个块维护一下块内最大值

当我们查询任意一个区间[l,r]时，如果l所在的块与r所在的块相同，如[1,2]，则直接暴力查询即可，时间复杂度O(√n)

若其不在一个块但是块是相邻的，一样是暴力查询，时间复杂度O(√n)

若其块不相邻，如[1,10]，我们先处理两边的边块角块，先暴力查询1和10所在的块内最大值，最后直接查询中间块内最大值即可，时间复杂度O(√n)

所以总时间复杂度O(√n)

那如果加入了区间修改，又该怎么办呢？

我还是不用线段树(当然也不用树套树)

对于整块修改，我们打个加法标记，即当前块增加了多少，最大值相应的就增加了多少

而多于边块角块，暴力修改，特判最大值即可

所以总时间复杂度也是O(√n)

分块还能解决很多很麻烦的问题，比如寻找区间内前驱后继

我会树套树！

不好意思树套树太麻烦了

分块解法也非常的好理解，当我们分块的时候，就对每一个块进行排序，查找时，边块角块依旧暴力，整块使用lower_bound和upper_bound二分查找即可

举个例子 LOJ6279（https://www.luogu.org/paste/2gc9ut9h）

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

此题查找前驱，我们直接使用上述算法即可

注意，边块角块修改后所在块要重新排序

分块的实质

分块其实是一种树形结构，它是一种只有三层的树，形态如下：

分块算法的延申

• 莫队

莫队算法的思路是，离线情况下对所有的询问进行一个sort()，然后两个指针l,r（本题是两个，其他的题可能会更多不断以看似暴力的方式在区间内跳来跳去，最终输出答案。
掌握一个思想基础：两个询问之间的状态跳转。如图，当前完成的询问的区间为[a,b],下一个询问的区间为[p,q],现在保存[a,b]区间内的每个颜色出现次数的sum[]数组已经准备好，[a,b]区间询问的答案Ans1已经准备好，怎样用这些条件求出[p,q]区间询问的Ans2？

我们用分块的方式，来查询被修改了的值，将重新寻找区间最值的复杂度降到了一个非常低的水平，这就是分块在莫队中的应用。

例题：洛谷P1494，可作为莫队入门题

莫队的时间复杂度均摊为O(n^{3/2})

本文发布于洛谷日报，特约作者：刘浩宇（寂）

原文地址：https://www.luogu.org/blog/48265/qian-tan-ji-chu-gen-hao-suan-fa-fen-kuai