根号数据结构

序列分块

通过将序列分成小段，整块标记，不足整块的暴力，以平衡修改查询的复杂度。

如果两个操作的调用次数有较大差异，可以使用分块维护更多/更少信息来平衡两边的时间复杂度。请注意并非选择“更快”的数据结构就更好，比如树状数组看似更平衡，但是修改和询问的次数不平衡的时候反而不合适。

如果想要不平衡的区间加区间求和，可以把树状数组的那个做法搬到分块上

• LOJ 6278/6279

分块做法

每一个块都维护一个排好序的数组，扫过整块的时候二分，修改的时候整块打 tag，不完整的块就暴力做，然后重新排序。\(\mathcal O(\sqrt n\log n)\)

归并做法

重新排序可以这样做：如果为排序后的数组保存一个 pos，每次修改把排序后数组分开，两边都是有序的，然后用归并排序进行 merge。这时候这一部分就优化为 \(\mathcal O(\sqrt n)\)

现在修改是 \(\mathcal O(S+n/S)\) 查询是 \(\mathcal O(S+n/S\log S)\)

令块长为 \(S=\sqrt{n\log n}\)

• LOJ 6284

事实上，每个整块被查一次之后就肯定变成同一个了。每次询问会增加 \(\mathcal O(1)\) 个坏的块，总共可能产生 \(\mathcal O(\sqrt n+m)\) 个坏的块，总复杂度就是对的。

• P4117

考虑每个数可以被操作的次数有限，故记录每个块的最大值。考虑如何能够均摊 \(\mathcal O(1)\) 枚举，所以我们的目标是某一个值域被枚举之后就不要再枚举它，我们发现当 \(2x\ge max\) 的时候是 ok 的，但是小的时候，我们就亏了，所以有一个技巧是对大的减转化为对全局减对小的加，相当于维护了一个取值区间，分情况提高最小值、减小最大值。

这里还有空间的问题，我们发现每一个块的贡献皆独立，所以我们可以对于每一块跑一遍所有询问，这样桶就可以被重复使用。

值域/操作分块

1. 对值域数组的分块

2. 操作分块（按时间分块）：操作和询问按照时间分为若干块，对于前面所有块，我们把那些影响直接贡献到一个支持快速查询的数据结构上，内部的修改我们只计算他对询问的贡献，这个块的询问跑完之后再固定到数据结构上。

• 1

我们先 \(\mathcal O(nk)\) 得到单点修改之后 delta 的表示。这样可以 \(\mathcal O(1)\) 计算贡献。现在考虑如何固定影响，考虑直接求一遍。

令块长为 \(S\) ，则 \(\mathcal O(nS+kn\frac{n}S)\) ，\(S=\sqrt{nk}\)

• 2: APIO2019 桥梁

没有修改，可以用并查集。这里并不好计算修改对答案的贡献，但是可以利用块内修改很少的特点

3. DFS 序分块

对树的 DFS 序进行序列分块。

4. 重链剖分+序列分块

对一条长为 \(k\) 的重链进行序列分块，按 \(\sqrt k\) 分块 ，用于优化链修改链查询，不能做子树操作。

• CF925E May Holidays

先转化为链操作，赋予每一个点 \(-v_i\) 的权，考虑进行树链分块。加1减1操作有特殊性，把相邻的数合并之后，我们可以不用二分，只需要维护一个指针。然后边块修改的时候可以用归并，单点修改的时候暴力加了之后二分一下然后插入。

5. 简易树分块

在 \(n\) 个点的树上随机撒 \(\sqrt n\) 个点，期望两个关键点之间距离期望为 \(\sqrt n\)

贪心可以将这个变成严格的：按深度排序从大到小扫，若没有标记，就设为关键点并向上跳 \(\sqrt n\) 到另一个点，设为关键点，并把子树内所有点标记了。注意这样需要额外空间。

也可以把关键点的虚树上的点也记作关键点。

只能处理链操作。

• SDOI2022 无处存储

本题是树分块，那是因为本题卡空间