浅谈基础根号算法——分块

decoqwq

2018-07-14 12:10:34

Algo. & Theory

已update(感谢codesonic添加qwq)

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

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

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

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

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

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

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

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

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

int n;//总个数
int block=sqrt(n);//每一块大小
for(int i=1;i<=n;i++)
{
    belong[i]=(i-1)/block+1;//每一个数所在块
}

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

我们举个例子:

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

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

但是拿分块又怎么做呢？

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

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

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

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

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

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

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

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

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

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

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

我会树套树！

不好意思树套树太麻烦了

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

举个例子 LOJ6279

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

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

代码见这里

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

分块的实质

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

第一层为整个序列，第二层为\sqrt n个大小为\sqrt n的序列(近似)，第三层为n个大小为1的序列

分块算法的延申

莫队

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

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

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

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

带修莫队

带修莫队，是建立于莫队基础之上的一种算法。当原序列值受到改变时，莫队中存储的答案必定会改变，那么我们如何避免修改操作带来的影响呢？

首先我们需要把查询操作和修改操作分别记录下来。

在记录查询操作的时候，需要增加一个变量来记录离本次查询最近的修改的位置，你需要一个变量记录现在已经做了几次修改。如果改多了，你就要改回去qwq

所以可以得到带修改的莫对分为三维，左指针，右指针，以及当前修改次数

和普通莫队一样，我们先对所有操作sort一遍后，每次再查询，代码则变成了

/*基础莫队操作*/
while(l<Q[i].x) Delet(a[l++]);
while(l>Q[i].x) Add(a[--l]);
while(r<Q[i].y) Add(a[++r]);
while(r>Q[i].y) Delet(a[r--]);
/*基础莫队操作*/
/*继续修改的操作*/
while(now<Q[i].pre) Work(++now,i);
while(now>Q[i].pre) Work(now--,i);
/*修改回去的操作*/
out[Q[i].id]=ans;//统计答案

均摊时间复杂度因为修改的存在，变为了O(n^{5/3})

例题：洛谷P3939，可直接跑带修莫队