fusion tree(1990)

· · 算法·理论

upd on 25.5.24：提交了本文。我感觉玩 WRM 很有意思，但莫得前途。

参考了原论文和 lxl 写的介绍。怎么感觉我现在完全是贺的啊喂！

关于 builtin 系列函数，我们的硬件完全可以支持，不妨认为这个是 O(1) 的。当然只求前驱后继并不需要这个，查排名相关的就不妙了。所以原论文实际上没写可以查排名相关，使用的时候要小心谨慎。

融合树可以在 O(\log n/\log w+\log w) 的时间维护动态集合，即插入，删除，求前驱、后继、排名和排名为 x 的数。注意这里的 n 是集合大小。

据说 WRM 下维护动态集合的复杂度下界是 \Omega(\log n/\log w)，这个在 2014 年 Mihai Patrascu 和 Mikkel Thorup 的论文中被做到。

如果有一种方法能维护大小为 B=\text{poly} \ w 的静态集合，支持 \text{poly}\ B 时间预处理，O(1) 在集合里面 lower-bound，那就达到目标了。

具体的，建个 w^{\epsilon} 叉的 B-树，就可以 O(\log n/\log w) 检索。然后设插入复杂度是 O(x)（x=\text{poly}\ w），我们对集合的排序数组维护个大小为 x 的块链，只把每个块中的一个元素丢到上面的数据结构里面，每块内用平衡树维护。插入的时候进行一次查询以确定丢到哪个块里面。

这样做的复杂度就是 O(\log n/\log w+\log w)。

fusion tree 的核心就在这个 O(B^4) 预处理 O(1) lower-bound。

现在集合 S 大小 B=w^{1/5}。

对 x\ne y 定义 msb(x,y) 为 x,y 的最高的不同的位。定义集合 c=\{msb(x,y)|x,y\in S\}。|c|=O(B)，因为这相当于 S 的 01-trie 上有两个儿子的结点的高度集合。

值得注意的是，如果不用 builtin 系列函数而是利用乘法，这个 msb 是可以在 \text{poly}(w) 的时间预处理 O(1) 查询的。可以在这里查看。

考虑把 S 中的数只保留 c 中的位（即每个数有 r=|c| 位），得到一个新集合 S'。显然 S 和 S' 中对应数的大小关系是一致的。

现在要对一个 x 做 lower-bound。考虑把 x 保留 c 中的位得到 x'。对 x' 在这个压缩后的集合 S' 中做 lower-bound 应该是相对平凡的。现在假设我们得到了 x' 在 S' 中的前驱后继 u',v'，我们考虑其对应的 S 中的数 u,v。

如果 u\le x\le v 就行了。否则请想象这个 01-trie。这意味着在某条单链上，我们走错了。那么 u 和 v 是一定包含这个走错的位置的。求出这个走错的位置后，因为他在单链上走错了，接下来他怎么走是无所谓的，所以其排名就是其最近的分叉祖先对应儿子的排名。这个容易预处理。

技术细节 1

首先我们注意到，在 \text{poly} \ B 时间求出 x' 是困难的。实际上我们只需要把这 r 个位提取到一个 \text{poly} \ r 个位的数里面就行了。

记 c 中的数为 c_1<c_2<\dots <c_r，对于一个待提取的数 x：

先按位与一下使得 c 之外的位都是 0。然后我们的想法是把 x 乘上一个数，使得结果的所有位落在一个大小为 \text{poly} \ r 的区间中。再按位与一下只保留需要的这 r 位。

具体的，设这个数是 \sum_i 2^{m_i}，需要满足 c_i+m_j 两两不同，且 c_1+m_1<c_2+m_2<\dots <c_r+m_r，(c_r+m_r)-(c_1+m_1)=\text{poly}\ r。这里的 \text{poly}\ r=r^4。

考虑构造一个 m' 满足对于 i\ne j，c_p+m'_i\bmod r^3 和 c_q+m'_j\bmod r^3 不同，然后总是能够找到一组 m_i=m'_i+kr^3 满足 m_i+c_i-m_{i-1}-c_{i-1}\le r^3。构造 m' 是简单的，直接增量构造。每次新加一个 m' 至多新禁掉 r^2 个可行的 m，最后一次之前也只能禁掉 r^2(r-1) 个可行的 m'。这个构造是 O(r^4) 的。

技术细节 2

要在 S' 中 lower-bound。

记 S' 中每个数有 u 位，直接把 S' 里面每个数前面加个 1 连起来，查 x 的时候给 x 乘上个 \sum_i 2^{ui+1}，然后相减一下。这样 <x 的数对应的前面的 1 就会变成 0。提取一下这些位就行了。

技术细节 3

查排名相关的操作需要每次更新子树大小，可以使用一个 word 和定期重构前缀和维护。