分块

经典操作

暴力思想

先考虑最暴力的做法如何实现。

平衡思想

设长度 \(n\)，块长 \(B\)。

多数是定一个块长，使整块与散块、查询与修改的复杂度近似相等，并分别考虑整块好散块的情况。

暴力重构

指对散块处理时如果会破坏一个块的既有标记等等，可以选择暴力重新构建当前的标记。

复杂度分析

根据一次操作最多涉及两个散块，以及操作本身的性质，可以得到低于纸面复杂度的复杂度。

LOJ 数列分块入门

数列分块入门 1

区间加，单点查询。

查询复杂度为 \(O(1)\)，对散块修改复杂度 \(O(B)\)，对整块修改复杂度 \(O\left(\dfrac{n}{B}\right)\)，总复杂度 \(O\left(B+\dfrac{n}{B}\right)\)，显然 \(B\) 取 \(\sqrt{n}\)。

数列分块入门 2

区间加，区间查小于某个值的个数。

最暴力做法是直接排序然后二分，考虑分块排序。

区间加对整块没有影响，对散块的影响一次只有两个，于是每次暴力重构这两个散块。

修改复杂度 \(O\left(B\log B +\dfrac{n}{B}\right)\)，查询复杂度 \(O\left(B\log B+\dfrac{n}{B}\log \dfrac{n}{B}\right)\)，\(B\) 取 \(\sqrt{n}\)。

数列分块入门 3

区间加，区间查前驱。

和上一题类似，暴力排序查前驱取最大值，复杂度相同。

数列分块入门 4

区间加，区间求和。

比较平凡，散块 \(O(B)\)，整块 \(O\left(\dfrac{n}{B}\right)\)，只有加法标记所以不用下传。

数列分块入门 5

区间开方，区间求和。

单点开方只需要 \(O(\log \log a)\) 次，对整块的每次操作都开方，每个块最劣复杂度 \(O(B^2\log\log a)\)，总体复杂度 \(O\left(\dfrac{n}{B}\times B^2\log\log a\right)\)，取 \(B=\sqrt{n}\)。

数列分块入门 6

单点插入，单点查询。

使用块状链表，类似于链表套链表，维持每个块的链表大小不超过 \(2\sqrt{n}\)，这样复杂度降到了 \(O(\sqrt{n})\)。

数列分块入门 7

区间加，区间乘，单点查询。

乘法的加入使得散块修改会破坏懒标记，于是暴力重构。

数列分块入门 8

区间查询出现次数并赋值。

两个操作放在一起，设想暴力查询并赋值，整块赋值打上标记，这样每个块处理第一次被完全扫过之后，只有一部分作为散块被处理才需要再下一次经过是再扫一遍。于是每次操作只会增加两个块需要被完全扫过，复杂度是正确的。

数列分块入门 9

区间最小众数。

一个重要性质：两个区间的众数要么来自前者的众数要么来自后者中的元素。

预处理由整块组成的所有区间的众数。当合并区间时，大区间的众数已知，新扩展的一个块中每个元素的出现次数可以二分查询（也可以前缀和）。

这样询问时，整块部分已知，同样是将两个散块中的元素查询出现次数并比较。

值域分块

可以用于查询区间第 \(k\) 大等问题。

正常的数列分块中，我们可以暴力维护块内排好序的数据，但是查询时需要二分答案，复杂度多一个 \(\log\)。

如果对值域分块，每个块维护该值域内的个数，可以 \(O(\sqrt{n})\) 确定第 \(k\) 对应的块，再 \(O(\sqrt{n})\) 扫过这个块求出答案。

对值域分块与数列分块的关系可以类比权值线段树与普通线段树的关系，前者处理排名前驱后继等更为优秀，后者则是便于处理关于区间和、积等等。

莫队

普通莫队

概述

不带修，实际上是以一种排序方式使看似暴力的做法复杂度变优秀。

对于一类区间询问问题，如果可以以 \(O(k)\) 的复杂度将区间左右指针移动一位，那么按照某种方法排序可以做到 \(O(n\sqrt{n}\times k)\)。

排序方法是：对序列分块，以左端点所在块为第一关键字升序排序，以右端点为第二关键字排序（奇数块升序偶数块降序）。

时间复杂度

设块长 \(B\)，假设移动指针 \(O(1)\)，分别考虑左右指针移动复杂度。

左指针在同一个块内，右指针最劣情况是移动 \(O(n)\)，总复杂度是 \(O\left(\dfrac{n^2}{B}\right)\)，左指针最劣情况是每次都移动 \(O(B)\)，总复杂度是 \(O(nB)\)，取 \(B=\sqrt{n}\)，则算法复杂度是 \(O(n\sqrt{n})\)。

常数优化

在排序时，注意到第二关键字讨论了块的奇偶性，这使得我们升序扫完奇数块后，右端点左移的过程中已经开始处理偶数块，可以优化常数。

端点伸缩的顺序

可能会出现先缩小左区间再扩大右区间而导致当前的端点 \(l>r\)，从而删去未加入的数据而导致错误。

保证正确且容易记住的顺序是：先扩大区间后缩小，先左端点后右端点。

带修莫队

概述

增加一维时间，需要改变排序方式。

以左端点所在块为第一关键字升序排序，以右端点所在块为第二关键字升序排序，以时间为第三关键字升序排序。

这样在处理每个询问时先移动左右指针，再移动时间指针并判断当前修改是否在左右指针范围内。

时间复杂度

左指针：同样是每次最劣移动 \(O(B)\)，总复杂度 \(O(nB)\)。
右指针：左指针在同一个块时移动 \(O(nB)\)，左指针改变块时移动 \(O\left(\dfrac{n^2}{B}\right)\)。
时间指针：左右指针共构成 \(\dfrac{n^2}{B^2}\) 个块，最劣情况时每次移动 \(O(n)\)，总复杂度 \(O\left(\dfrac{n^3}{B^2}\right)\)。