对祂使用根号平衡吧（十二重分块法）

jerry1717 · 2026-04-19 20:38:36 · 算法·理论

前置知识：基础分块（会做分块入门九题的一半即可）。

你经常会因为写出诡异 O(n \sqrt{n \log n}) 却不会优化而被卡掉，你可能需要我们伟大的根号平衡大人。啊，我们的根号平衡大人，平等的为每个执着于祂的人献上最美丽的根号算法。这就是我们块门啊！

以下默认 x 为单点修改的编号，l,r 为查询或询问的左右端点。

1. 单点修改 O(\sqrt n)，区间查询 O(1)

可以证明，这种状物都可做，而且非常常用，我们一步步由浅入深。

1.1 单点修改，区间和

相当常见的平衡，考虑将序列按 O(\sqrt n) 分块。

然后你对每一个块储存一个 sum_i 表示前 i 块的和。然后再存 pre_{i,j} 表示第 i 块中前 j 个数的和。

记查询左端点块编号为 L，右端点块编号为 R。

查询结果即为 sum_{R-1}-sum_{L-1}+pre_{R,r}-pre_{L,l-1}，注意是 sum_{L-1}，因为从 l 到 L 的右端点这一段也是要统计的。

修改的话先还原前缀和，然后修改 x 所在块的 sum，再做一次前缀和就修改了 sum 数组。然后 pre 数组直接暴力在块内修改即可。

读者可以自行探究常数较小的写法

1.2 单点修改，区间最值

沿用上一题的思路，先按 \sqrt n 进行分块，然后对块内维护 maxx_i,pre_{i,j},suf_{i,j} 分别表示第 i 块的最值，第 i 块前 j 个数的最值和第 i 块后 j 个数的最值，这些东西显然都可以直接暴力在块内维护。

那我们现在需要维护一个什么东西？我们采用抽象思维，等价于维护一个长为 \sqrt n 的数组，单点修改，区间最值。

只要会做这个我们直接沿用在整块和散块上就好了。

我们发现有一个东西叫 ST 表，但是在我们印象中这个东西貌似不支持修改……吗？

你分析以下复杂度，你对 x 修改，那么对第 y 个位置（y<x）就只需要修改 \log (n-y+x) 位。那么总复杂度就是 \sum_{i=1}^{\log n} (\log n - i + 1) \times 2^i，我是低手，我不会分析这个。

但是有更简单的分析方式，你考虑长度为 2^i 的区间只有 2^i 个包含了 x，那么，你直接修改就有 \sum 2^i 个区间需要修改，这不就显然是 O(\sqrt n) 复杂度的？

注意到同机房大手子们还成功胡出了对于每个块重构时用四毛子直接重构，还有什么 n^{0.75},n^{0.5},n^{0.25} 分三次块的诡异做法，吓哭了。

1.3 单点修改，区间半群

区间半群没有什么良好的性质，没法建出 ST 表。

你还是和上面一样做，最后还是要维护一个长为 \sqrt n 的数组，单点修改，区间半群。

诶呀，你发现我们上面提出一个子问题恰好是原命题的 \sqrt n 版本对不对，那你直接递归下去是不是就对完了。

由此，我们需要知道 n 需要开根号能开 \log \log n 次，这样我们的复杂度就变为了 O(n \log \log n) 预处理，O(\sqrt n) 修改,O(\log \log n) 查询。

实际上还可以用 Sqrt Tree 相关理论优化查询复杂度，但是没有意义（在信奥条件下 \log \log n \le 6）且太过于复杂。

2. 单点修改 O(1)，区间查询 O(\sqrt n)

貌似比较神秘。

2.1 单点加，区间和

对于每个块维护 sum_i 表示第 i 块的和。

然后区间查询直接扫一遍每个块，再把散块加上就好了。

2.2 单点加正数，区间最大值

你考虑一个区间的正数只会变大。

那么维护一个 maxx_i 表示第 i 块的最大值，那么 maxx_i 在修改过程中不会变小，对于修改所处的块，可以直接算出来修改后的块内最大值，于是可以轻松修改。

查询还是扫一遍每个整块，再对每个散块取最大值。

2.3 单点改为小于最小值的数，区间最大值

考虑每个块全部开一个单调队列，队首即为最大值，因为每次越改越小，所以直接插入到队尾就做完了。

2.4 单点改，区间最大值

其实是为了这醋包的饺子。

考虑单点修改可以理解成删除一个位置，然后插入一个数。

先光速做掉散块，这一部分是简单的。

考虑我全程没有说强制在线，所以是离线的。

转化一下题意，即有 O(n\sqrt n) 次修改，O(n) 次查询。

首先对于每一个块做出块内最大值，然后删除什么的你开一个链表状物，每次删除直接删，你这样直接就是 O(1) 的。

然后加入一个数直接塞到这个数组的末尾，称这些数为散点。

当散点个数不超过 O(\sqrt n) 时，你直接暴力枚举最后的所有散点就是 O(\sqrt n) 的。超过 O(\sqrt n) 时你直接重构一个块，超过 O(\sqrt n) 个块就整体重新划分。

你遇到了一个问题，在新构成的块中是有下标限制的，相当于你还要 O(n) 做块内 ST 表，但是这个 ST 表还要支持 O(1) 删除！

其实可做，你首先在块内使用基数排序，这个排序按下标来排，然后进行诡异多层分块，每层分块都排序，然后维护一个懒标记删除，查询时再删。

查询就先访问每个散点，直接二分每一个块的区间，然后做多层分块找最大值这个操作，为优化二分复杂度，我们采用分散层叠。

已经很难分析复杂度了，大概是 O(1) 修改，O(n^{\frac{1}{2}+\epsilon}) 查询的。

然后我们进行更加抽象的操作，考虑改我们的询问分块为多层分块，可以做到 O(n^{\epsilon}) 查询。

可能讲的不太清楚，大家可以学习这篇文章。

3. 非常规类型

3.1 区间加，区间和

考虑如何用树状数组来做区间加，区间和。

你发现可以通过维护差分数组 b，只需要维护 \sum b_i 和 \sum b_i \times i 就可以运用加加减减计算出一段区间的答案。

欸，那这样不就转化成了单点修改，前缀和吗？

套用 1.1 和 2.1 的算法可以做到 O(1) 修改，O(\sqrt n) 查询与 O(\sqrt n) 修改，O(1) 查询。

3.2 树链加，子树和

与 3.1 一样，我们考虑维护 b_i 表示为 a_i-a_{fa_i}，这样我们一样维护 \sum b_i 和 \sum b_i \times dep_i，一样加加减减一下，就可以知道等价于单点修改，子树和。

众所周知子树和拍成欧拉序可以转化为 1.1 或 2.1。

3.3 单点改 O(1)，全局 k 小 O(\sqrt n)

直接对整个数组做一次值域分块，然后你考虑你需要在分块上实现线段树二分。

于是考虑从小到大枚举每一个块，如果这个块内的值加上前面的值还是小于 k，就遍历下一个块，否则就进入散块，枚举散块的值，直接做就好了。

3.4 单点改 O(\sqrt n)，全局 k 小 O(1)

考虑这就是维护一个排好序的数组，直接使用分块块状物维护。因为单点修改反而有良好的性质，即一共有 n 个值。那么单点修改相当于把一个位置挪到某个位置。

于是每个块开一个长为严格 \sqrt n 的数组，散块直接暴力维护，整块可先记录一个偏移量，如果改了 O(\sqrt n) 次了就整体重构一下保证正确性，可能需要处理周围的 O(1) 个块，感觉细节很多。

这一段是我现胡的，如果有问题欢迎骂死我。

3.5 单点加，矩阵和

注意，给定的关键点集合需要是一个排列。

考虑分出 n^{0.75} \times n^{0.75} 的块，同时分 n^{0.5} \times n^{0.75} 和 n^{0.75} \times n^{0.5} 与 n^{0.5} \times n^{0.5} 的块。

然后你就使用拼好块手法，一块一块的拼起来，如图：

观测到所有颜色的块数量都是 O(\sqrt n) 的。

对于最旁边紫色的散块，这其中只有 O(\sqrt n) 个点（是个排列），直接暴力做就完了。

所以 O(1) - O(\sqrt n) 与 O(\sqrt n) - O(1) 都是简单的。

4. 例题

尾声

愿根号救赎你。