Sqrt tree 学习笔记

博客园同步

前置知识

你首先要学会的：

• $\text{RMQ}(ST \text{表})$RMQ(ST表)
• 分块
• 线段树
• 二进制，位运算

前记

我们把 $\text{RMQ}$RMQ 和分块 所解决的问题搬出来：

• 在长度为 $n$n 的数组上，$T$T 组询问 $[l,r]$[l,r] 区间的 和（差，异或等有结合律的算术）。

显然我们已经有了一个 $\mathcal{O}(n \log n) - \mathcal{O}(1)$O(nlogn)−O(1) 的算法。

思考

现在做一个 简单 的加强，$n,T \leq 2 \times 10^7$n,T≤2×107.

你会发现预处理的时间不够了。

很显然，我们考虑朴素的分块怎么做。

将数组分为若干个长度为 $b$b 的块，对于每个块，处理块内答案，前缀块的答案，后缀块的答案。

当 $b = \sqrt{n}$b=n​ 时 取到最平均的答案，可以 $\mathcal{O}(n) - \mathcal{O}(\sqrt{n})$O(n)−O(n​)，但显然不行。

那考虑 $\text{RMQ}$RMQ 呢？用 $f_{i,j}$fi,j​ 表示 $[i , i + 2^j-1]$[i,i+2j−1] 区间的答案，倍增处理即可。显然是 $\mathcal{O}(n \log n) - \mathcal{O}(1)$O(nlogn)−O(1).

这两个算法都无法通过 $2 \times 10^7$2×107 如此庞大的数据。我们思考一个新的算法。

基于分块

首先考虑分块基础上的优化。同样 处理块内答案，前缀块的答案，后缀块的答案，这里是 $\mathcal{O}(n)$O(n) 的，考虑如何优化询问。

询问分两种情况：

• 横跨多个块
• 包含在一个块内

显然，第一种情况我们可以把 横跨的整块 进行前缀计算，然后转为 对两侧不完整快的计算，即剩余两个部分各自包含在一个完整的块内。这样做是 $\mathcal{O}(1)$O(1) 的，但如何计算第二种方案？

考虑如何处理一个块内的方案，如果按照 分块的暴力思想，那么 $\mathcal{O}(\sqrt{n})$O(n​) 就奠定了。显然这不是我们想要的。

现在的问题转为，在长度为 $\sqrt{n}$n​ 的数组上，$T$T 组询问 $[l,r]$[l,r] 区间的 和（差，异或等有结合律的算术）。

咦？这不是分块吗？

人见人爱的 分块套分块 又重出江湖了？

我们可以设法将 $\sqrt{n}$n​ 长的块进行再分块，分为 $\sqrt{\sqrt{n}}$n​​ 长的块，然后再不断往下分 $\cdots \cdots$⋯⋯ 直到块长为 $1$1 为止。

首先，似乎这样的时间复杂度很稳，$\mathcal{O}(n + \sqrt{n} + \sqrt{\sqrt{n}} + \cdots \cdots) = \mathcal{O}(n)$O(n+n​+n​​+⋯⋯)=O(n)，但空间上无法承受，需要处理的区间太多。

既然分块失败了，我们考虑在分块的基础上，思考新的算法。

$\texttt{Sqrt tree}$Sqrt tree 的建树

俗语云：“智商不够，数据结构来凑”。

现在我们想的一种 基于递归，搜索 的算法，能否有数据结构与其接轨呢？

显然，我们可以用 树 来实现。

对长度为 $k$k 的区间，将其分裂为 $\sqrt{k}$k​ 个长 $\sqrt{k}$k​ 的子区间，即有 $\sqrt{k}$k​ 个儿子。叶子节点的长度为 $1$1 或 $2$2.

第一层的节点维护 $[1,n]$[1,n] 的答案。

假想一下：如果这棵树只建立 $2$2 层，可以认为和 朴素分块 没有任何区别。

显然我们建完这棵树后，应当考虑复杂度怎样。

整棵树的高度是 $\mathcal{O(\log \log n)}$O(loglogn) 的，每层区间总长为 $n$n，建树的时间复杂度为 $\mathcal{O(n \log \log n)}$O(nloglogn)，可以接受。而空间上也可以接受。

那么问题来了：在这样类似于 线段树 的数据结构上，如何询问呢？

$\text{Sqrt tree}$Sqrt tree 的询问

在树高为 $\mathcal{O}(\log \log n)$O(loglogn) 的树上，按照线段树的思想，显然单次查询是 $\mathcal{O}(\log \log n)$O(loglogn) 的。这样并不优。

如何优化？

$\text{Sqrt tree}$Sqrt tree 的询问优化

其实瓶颈在于如何快速确定树高。树高很好确定，直接二分就行。那么这样就变成了 $\mathcal{O}(\log \log \log n)$O(logloglogn).

对于 $n = 2 \times 10^7$n=2×107，这个数已经变成了近似 $2$2，几乎 可以视为常数。

我们考虑如何把这个数彻底地降为 $\mathcal{O}(1)$O(1)，以免夜长梦多！

$\text{Sqrt tree}$Sqrt tree 的询问再优化

精髓来了。

上面我们已经做到了 $\mathcal{O}(n \log \log n) - \mathcal{O}(\log \log \log n)$O(nloglogn)−O(logloglogn) 的算法，我们试图做到一个 $\mathcal{O}(n \log \log n) - \mathcal{O}(1)$O(nloglogn)−O(1).

思考一下：$\text{RMQ}$RMQ 的预处理，如果你在询问的时候暴力倍增，不也是 $\mathcal{O}(\log n)$O(logn) 吗？最后我们用 二进制 的特效完成了从 $\mathcal{O}(\log n)$O(logn) 到 $\mathcal{O}(1)$O(1) 的跳跃，让 $\text{RMQ}$RMQ 彻彻底底的战胜了 线段树（只是在两者都能解决的领域）。

现在我们仍要运用这个黑科技，二进制的运算从来不庸俗。

所以，按照 $\text{OI Wiki}$OI Wiki 的说法，

非常形象。如果你觉得这些太枯燥，我们来简单解释一下。

首先假设所有区间的长度都可以表示为 $2^t (t为自然数)$2t(t为自然数) 的形式，对于不满足的区间我们可以在后面添上一些 不影响运算 的数值，在 $+$+ 中可以是 $0$0. 由于区间的增大最多 $\times 2$×2 不到，因此不影响复杂度。

这样我们可以来用二进制了。首先我们把端点写成二进制的形式，由于每个块长度一样，端点呈 等差 形式，因此 每个块的两个端点的二进制有且仅有后 $k$k 位不同。所以显然的，我们预处理的时候可以求出 $k$k，并可以 $\mathcal{O}(1)$O(1) 计算 当前区间两个端点的二进制值。

如何判断当前区间是否涵盖在一个块里？显然这个问题就变成，当前取件两个端点的二进制是否只有后 $k$k 位不同。这个问题不难解决。我们只需要将区间两端进行 异或操作，判断是否 $\leq 2^k-1$≤2k−1 即可。

那么如何快速找到树高呢（即对应再第几层）？对当前 $[l,r]$[l,r] 计算最高位上的 $1$1 的位置，并处理 $i \in [1,n]$i∈[1,n] 中 $i$i 的最高位上 $1$1 的位置。这样可以 $\mathcal{O}(1)$O(1) 计算树高，$\mathcal{O}(1)$O(1) 查询啦！

这就是 $\text{Sqrt tree}$Sqrt tree，可以实现 $\mathcal{O}(n \log \log n) - \mathcal{O}(1)$O(nloglogn)−O(1).

可能你会说，$\mathcal{O}(n \log \log n)$O(nloglogn) 对于 $n = 2 \times 10^7$n=2×107 会跑到 $10^8$108 左右，不稳。

$\mathcal{O}(n \log n) - \mathcal{O}(1)$O(nlogn)−O(1) 就稳了？

$\mathcal{O(n) - \mathcal{O}(\sqrt{n})}$O(n)−O(n​) 就稳了？

显然 $\text{Sqrt tree}$Sqrt tree 已经是此类问题最优的算法，没有之一！

$\text{Sqrt tree}$Sqrt tree 的修改

现在出题人意外地发现你用 不带修改 的简单 $\text{Sqrt tree}$Sqrt tree 模板切题了！

出题人非常生气，毫不客气地加上了这样一句话：

• 每次操作分询问和修改两种。

那么如何修改呢？

直接在 $\text{Sqrt tree}$Sqrt tree 上暴力？

$\text{Sqrt tree}$Sqrt tree 的单点修改

首先考虑单点如何修改 $a_x = val$ax​=val。

暴力的话，我们需要更改树上含 $x$x 的区间，显然我们需要重新计算的区间为：

$\mathcal{O}(n + \sqrt{n} + \sqrt{\sqrt{n}} + \cdots \cdots) = \mathcal{O}(n)$O(n+n​+n​​+⋯⋯)=O(n)

但是你觉得这样很满足吗？那出题人给你个修改都要 $\mathcal{O}(n)$O(n)，岂不是要让 $\mathcal{O}(nT)$O(nT) 的暴力通过了？

$\text{Sqrt tree}$Sqrt tree 的单点修改优化

类似于线段树吧，可以打 $\text{lazy\_tag}$lazy_tag，不必完全暴力的。

这里引进 $\text{Index}$Index 的概念，记录每个区间被修改的块编号。

那么 $\mathcal{O}(\sqrt{n})$O(n​) 很稳。但是这样询问也增加了复杂度。

$\text{Sqrt tree}$Sqrt tree 的区间修改

考虑如何将 $[l,r]$[l,r] 的所有数都改成 $x$x.

我们已经有了以下的算法（修改 - 查询）：

$\mathcal{O}(\sqrt{n} \log \log n) - \mathcal{O}(1)$O(n​loglogn)−O(1)

$\mathcal{O}(\sqrt{n}) - \mathcal{O}(\log \log n)$O(n​)−O(loglogn)

下面会一一解释这两种实现。

区间修改的第一种实现

第一种实现中，把第一层 被 $[l,r]$[l,r] 完全覆盖的区间 打上标记。

两侧的块修改一部分，没有办法，只能暴力，$\mathcal{O}(\sqrt{n} \log \log n)$O(n​loglogn).

查询的话，直接去 $\text{Index}$Index 里查询，$\mathcal{O}(1)$O(1).

区间修改的第二种实现

每个节点都会被打上标记，那么每次询问要把祖先的标记更新一遍，就会形成 $\mathcal{O}(\sqrt{n}) - \mathcal{O}(\log \log n)$O(n​)−O(loglogn) 的复杂度。

总结

$\text{Sqrt tree}$Sqrt tree 在不带修改的情况下效率比 线段树 要高很多，但是实现的功能不如 线段树 多（比方说线段树可以维护 $\text{LIS}$LIS）；

带修改时，$\text{RMQ}$RMQ 无疑最优，其次是 线段树，然后是分块和 $\text{Sqrt tree}$Sqrt tree.

$\text{OI}$OI 中不常考，但希望大家掌握。

参考资料

$\text{Sqrt Tree - OI Wiki}$Sqrt Tree - OI Wiki

课后习题

洛谷 $\text{P3793}$P3793 由乃救爷爷