很久之前写的烂尾笔记

根号数据结构

简介

顾名思义，复杂度含 $O(\sqrt n)$ 的数据结构叫根号数据结构，一般都运用了分块和分值的思想。

分块

简介

分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度，或和其他算法搭配平衡出更优的时间复杂度。

使用分块进行维护对数据的特征要求较少 可以维护很多线段树无法维护的东西。

设块长为 $s$ ,复杂度 $O(n/s)$， $s$ 取 $\sqrt n$ 时最优，复杂度为 $O(\sqrt n)$ 。

缺点是 $O(\sqrt n)$ 的复杂度比 $O(\log n)$ 满了不少 但是在部分问题上分块在复杂度或者常数上优于 $O(\log ^2 n)$ 的树套树解法。

分类

序列分块

对于一个序列按每 $s$ 个元素进行分块，通过修改零散块内元素和修改整块元素去解决问题。

通常修改块内元素为暴力修改之后更新整块信息，修改整块元素则是以区间标记的形式修改。

值域分块

在值域上按每 $s$ 个元素进行分块，通过修改零散块内元素时修改整块元素去解决问题。

因为在值域本就存在一维偏序关系，即数据是有序的，所以可以依据序列分块的思想去解决问题。

通常用来平衡复杂度，例如 $O(1)$ 修改 $O(\sqrt n)$ 查询的全局最大值。

询问分块

对于每 $s$ 个询问进行分块，即一次处理 $s$ 个元素，同时进行 $n/s$ 次全局维护操作。

通常用于需要较大时间维护全局，但是可以以较小时间进行单次查询的问题，也是平衡复杂度的思想。

其他

例如块状链表等等。

莫队

简介

一种通过暴力移动端点去离线解决区间问题的方法。发明者为国集队长莫涛，所以被称为莫队。

算法发现过程 (大概?)

查询一个区间可以暴力的从左端点扫到右端点。当我们有两个区间 $[l_1,r_1]$ 和 $[l_2,r_2]$ 需要查询时且 $[l_1,r_1] \cap [l_2,r_2] \ne \emptyset$ 时，我们可以在扫描完 $[l_1,r_1]$ 之后继续从左到右扫描 $(r_1,r_2]$，同时撤销从左到右撤销 $[l_1,l_2)$。这种方式确实减少了扫描次数，但可以轻松构造数据使复杂度为 $O(n^2)$。

考虑分块的思想，限制端点移动范围。设块长为 $S$ ,对于 $l$ 在同一块内放在一起操作，同时按 $r$ 从小到大排序。这样 $l$ 在一次操作内最多移动 $S$ 次，$r$ 在同一块内最多移动 $n$ 次，所以 $l$ 的移动次数为 $m \cdot S$，$r$ 的移动次数为 $\dfrac{n^2}{S}$，这样复杂度为 $O(mS+\dfrac{n^2}{S})$。

可证在最优的情况下 $S$ 为 $\dfrac{n}{\sqrt m}$ 时最优。事实上如果对块长的设定不准确将会对复杂度造成很大影响，例如当 $m$ 与 $\sqrt n$ 同阶时，若将块长误设成 $\sqrt n$，复杂度将为$n \sqrt n$。

一些细节

• 莫队可以维护的数据需要支持在区间头或者尾加上或者删除,(也有不需要支持删除的莫队，详见回滚莫队)，比线段树之类的数据结构适用性更加更加广泛。
• 一般的莫队不支持修改 (也有支持修改的莫队，详见带修莫队)。
• 莫队是一种离线算法，对于强制在线的题目和信息学竞赛之外的方面应该没有啥用途。

板子题

小B的询问

[国家集训队] 小 Z 的袜子

分类

• 带修莫队
• 回滚莫队
• 莫队配合分块/bitset

带修莫队

简介

一般的莫队是无法支持修改的，因为一般无法做到在区间内修改快速更新 (要是可以就不需要莫队了)。及解决方法和 dp 类似，我们可以加一个维度。落实到带修莫队就是加一个时间维度，区间变为$[l,r,time]$。

转移和普通莫队一样转移，但是我们的排序多了一个关键字，以 $O(n^{\frac{2}{3}})$ 为一块，总复杂度为 $O(n^{\frac{5}{3}})$。

板子题

[国家集训队] 数颜色 / 维护队列

回滚莫队

简介

莫队配合分块 / bitse

板子题

曼哈顿交易 P3730 莫队+值域分块题解