融合树——Fusion Tree

1.前言：

Fusion Tree，中文译作融合树，是一种亚log的数据结构，与1993年由Michael L.Fredman和Dan E.Willard提出。

用途：O( \log n/ \log w+ \log w )时间复杂度支持插入，删除，前驱，后继，min，max，以及用于整数排序。

信息论断言对n个数的排序在最坏情况下需要n\log n次比较，不过对这个界我们还需要一些研究。

有人证明了任意unit cost RAM算法，其中只包含加法，减法，乘法，和0比较（但是不包含除法和位运算）最坏情况下需要\Omega(n\log n)的时间去对n个数排序。

如果允许使用除法和位运算，他们有一个线性时间复杂度的算法，但是这个算法对unit cost滥用。

这里我们规定我们使用的计算模型的字长是w，每个输入的数都是在[0,2^w-1]中的整数。

2.一些记号：

对于一个集合S和一个整数x，定义rank(S,x)为S集合中\le x的元素个数。 对于一些非负整数a，定义bin(a_1,...,a_n)=2^{a_i}+...+2^{a_n}。

对于两个非负整数a,b，定义msb(u,v)为u和v最高的不相同的位。

3.概述：

Fusion Tree大概可以看做是一棵特殊的B-Tree，特性：

1. 叉数B=O(w^{1/5})

2. 在一次搜索时，每个在搜索路径上的节点的正确的儿子可以被O(1)确定

从这些特性我们可以看出Fusion Tree单次操作的时间复杂度是O( \log _w(n) + \log w) = O( \log n/\log w +\log w)的，比O( \log n )低。

但是由于其实现方式，Fusion Tree每次对内部节点的更新复杂度是O( B^4 )的。 为了控制Fusion Tree均摊的更新复杂度，我们将这棵B-Tree的每对叶子节点之间的部分替换为一个大小大约为O( B^4 )的Weight Balanced Tree，只在WBT根节点发生变化的时候更新Fusion Tree的内部节点。

具体来说，我们B-Tree维护的是一个排序后的数组的分块，其中每个块都由一棵平衡二叉搜索树维护，fusion tree上只维护一个值来表示块边界，用途是指引每次插入，删除，查询在哪个块中。

可以发现这样我们把内部节点的变化次数除掉了一个B^4。

4.压缩key的表示：

如何O(1)确定搜索路径上的一个节点的正确的儿子：

考虑一个B-Tree的节点，其上面包含了k个key，其中B/2 \le k \le B，记作S={u_1,u_2,...u_k}。

然后我们定义出B(S)表示"有区别的位的位置"，用人话来说就是我们把这k个key的trie建出来，然后所有有超过1个儿子的节点的高度构成的集合 （当然这里我们不用把trie建出来，只是这么解释比较直观，而且更能反映出其的一些性质）。

再定义一个集合K(S)，为S只保留B(S)中那些位之后的值，记作K(S)={u'_1,u'_2,...u'_k}，发现这个压缩操作对于原集合是保序的。

对于一个任意的w-bit的数u，我们记u'(S)表示u只保留B(S)中那些位，即把非B(S)中的位都置为0之后的值。

下面引理表达了一个压缩key的重要性质：

引理1：

设B(S)排序后为c_1<c_2<...<c_r，定义边界c_0=-1,c_{r+1}=b。

定义u'_i为K(S)中任意的一个压缩后的key。

对于一个任意的w-bit的数u，满足u \neq u_i，

设msb(u'(S),u'_i)=c_m，即u和u_i在bit位置c_{m+1},...,c_r位置处相等，但是在c_m处不相等，如果u'(S)=u'_i，则我们记m=0。

如果u和u_i不同的最高位p满足p>c_m，那么我们可以通过：

1. 唯一的一个区间[c_{j-1},c_j]满足p属于这个区间

来确定rank(S,u)的值。

证明平凡，把trie画出来，显然可以画成一个平面图，然后可以发现这两个可以唯一地确定出一个平面区域，这个区域中的S集合元素个数就是rank(S,u)（感觉这种东西光写一堆自然语言也不能说明正确性，需要形式化证明一下？）。

注意到这个引理虽然是对任意u_i成立的，但是要求u和u_i不相同的最高位不是B(S)中的一个点，可以发现这个u_i其实必须在u"脱离"这个trie的位置，也就是p的父亲子树中。

引理1使得我们可以将rank(S,u)的计算规模降低到rank(K(S),u'(S))，通过计算rank(K(S),u'(S))，我们可以确定u'(S)在K(S)中的前驱后继u'_j和u'_{j+1}（这两个值不一定存在，但经过平凡的讨论就可以解决。

如果u_j \le u \le u_{j+1}，那我们已经解决了这个问题 否则我们令i=j或者i=j+1，计算出msb(u_i,u)=p，然后只要我们知道了包含p的区间[c_j,c_{j+1}]，我们就可以通过引理1来确定出rank(S,u)的值。

这里如果我们u_j \le u \le u_{j+1}，那我们已经达成了目的，不用继续考虑了。

否则如果不满足u_j \le u \le u_{j+1}，也就是说我们在这个sketch的过程中丢失了信息，即说明保留K(S)这些位的信息是不够的，那么p一定不在K(S)中，也就是说i=j和i=j+1中p较小的i满足p>c_m，故可以使用引理1。

计算K(S)和u'(S)： 我们发现没有平凡的方法可以将一个w-bit的数u在O(1)时间把B(S)那些位提取出来之后放到连续的一段中（可能可以通过硬件支持实现？），即使经过了一定预处理。

其实我们不需要做到这个，可以用具有：

1. 将需要提取出的位提取出，并放到（可以不连续）的更短的一段中

2. 保序性

的其他变化来实现我们需要的效果。

我们可以通过一次恰当的乘法和一次与运算来实现这个：

沿用引理1的定义，设我们需要从u中提取这些位，令C=bin(c_1,...,c_r)。

假设我们已经算出了C，我们先通过令v=u\;\mathrm{AND}\;C来将u中不需要的那些位置0。

然后我们将v乘以一个量M，从而把v中我们需要的那些bit转化到一个狭窄的范围内，然后再通过一次\mathrm{AND}来清除掉不需要的位置 这里给出对一个量M的存在性证明和构造：

记M=bin(m_1,...,m_r)，如果我们暂时忽略交叉和进位造成的影响，那么可以认为v乘M是把c_1,...c_r这些位置的位重新定位到了。

如果对任意$1 \le i,j \le r$，这$r^2$个$c_i+m_j$都是不同的，那么就不会发生交叉和进位了。 我们现在的目标是构造一个整数集合${m_1,...,m_r}$，使得： 1. $c_1+m_1<c_2+m_2<...<c_r+m_r

2. 对任意1 \le i,j \le r，c_i+m_j都是两两不同的。

3. 变换后的区间[c_1+m_1,c_r+m_r]"相对较小"，这里的相对较小其实只要是O( poly(r) )的即可，因为这样我们可以通过调整树的叉数来满足后续的条件。

引理2：

给一个r个整数的序列，c_1<...<c_r，存在一个r个整数的序列，m_1,...m_r，满足：

1. c_1+m_1<c_2+m_2<...<c_r+m_r

2. 对任意1 \le i,j \le r，c_i+m_j都是两两不同的。

3. (c_r+m_r)-(c_1+m_1) \le r^4

证明：

先考虑证明存在整数序列m'_1,...,m'_r，使得对任意i,j,a,b，m'_i+c_a与m'_j+c_b在模r^3的意义下不同余。

如果我们找到了这样的整数序列，那么所有r^2个c_i+m'_j都是两两不同的，并且由于这个是在模r^3意义下两两不同的，所以我们可以对第i个c_i+m'_i加上(i-1)*r^3，这样就可以保证对所有i满足c_i+m'_i<c_{i+1}+m'_{i+1}了。

关于m'_1,...,m'_r的存在性：

使用数学归纳法来证明，显然我们可以找到m'_1，这个平凡。

假设结论对t成立，即我们已经找到了m'_1,...,m'_t，满足对任意1 \le i,j \le t，a,b,有m'_i+c_a与m'_j+c_b在模r^3的意义下不同余。 可以观察到m'_{t+1}+c_i \equiv m'_s+c_j (\mod r^3\;)，即m'_{t+1} \equiv m'_s+c_j-c_i (\mod r^3\;)。

我们可以令m'_{t+1}是[0,r^3)中最小的和所有m'_s+c_j-c_i不同余的数，这里1 \le s \le t,1 \le i,j \le r。

由鸽巢原理，由于t*r^2<r^3，所以我们一定可以找到m'_{t+1}。

故当t+1 \le s时，结论对t+1成立 由数学归纳法知结论对s成立，同时我们这里给出了一个暴力的O( r^4 )的构造算法（r轮，每轮最坏枚举O( r^3 )个位置）。

5.融合：

融合树的"融合"即指将每个节点上的key放到同一个w-bit的word上，通过对这个word进行运算来一起处理这些key。

沿用之前u_i和B(S)=\{c_i\}的记号：

我们这个B-Tree的每个节点存了C=bin(c_1,...c_r)和M=bin(m_1,...,m_r)这两个量，用于计算u'(S)，同时还存了D=bin(c_1+m_1,...,c_r+m_r)这个量，用于清空u'(S)的计算中不需要的位。

同时还需要两个数组，存排序后的u_i和u'_i，和一个表f[i][j][2]表示引理1中，如果知道了u_i和j，还有u和u_i的大小关系，我们唯一确定的答案是多少。

回顾之前的内容，当我们算出了j=rank(K(S),u'(S))后，如果u不在[u_j,u_{j+1}]的区间中，那么我们把u'(S) \;\mathrm{XOR}\; u'_j和u'(S) \;\mathrm{XOR}\; u'_{j+1}比较一下，较小的值所对应的u'_h，h=j或j+1，和u有更长的公共前缀，即msb更小。

令m=msb(u,u_h)，然后我们需要知道m被哪个B(S)中的区间[c_i,c_{i+1}]包含，所以需要进行一次i=rank(B(S),m)的计算 还需要进行一次u和u_h的比较，这个平凡，当这些都做完了，我们查一下表f即可得到rank(S,u)。

可以发现fusion tree的每个内部节点需要存下O( B^2 )大小的表，内部节点个数是O( n/B^4 )个，所以是O( n )空间的。

下面给出对

1. rank(K(S),u'(S))

3. 两个w-bit的整数u,v，msb(u,v)

的计算方法：

O(1)计算rank(K(S),u'(S))：

我们把每个K(S)中的元素前面补一个1，然后从小到大拼到一起来，这个拼起来的操作就是所谓的"融合"。

由于我们K(S)中有k个元素，每个元素有r^4位，所以这里总共用了k(r^4+1)位，由于B/2 \le k \le B，所以我们总的位数是O( B^5 )的，由于B=O( w^{1/5} )，所以总的位数是O( w )的。

所以我们拼起来的这个东西是O( 1 )个word的，这里将其定义为A。

令C=\sum \limits _{i = 0} ^ {B} 2^{(r^4+1)i} 通过u'(S) \times C，可以将u'(S)前面补一个0之后复制B遍，然后拼到一起 通过A-u'(S) \times C，可以发现对每个A中补1的位置，其对应的那个u_i(S)如果<u'(S)，则这个1变成0，否则1不变 所以我们通过(A-u'(S) \times C)\&C，然后对这个word数1的个数即可知道rank(K(S),u'(S))。

由于这个word只在2^{(r^4+1)i}这样的位置有1，我们可以通过一次对2^{r^4+1}-1的取模来得到其中1的个数，虽然对常数取模可以用乘法和位运算O(1)实现，但我们这里可以给出一个更合适的构造。

我们可以通过将其乘C \& (2^{(r^4+1)k}-1)，这样相当于把其叠加了k次之后加起来，可以发现其中有一个长为r^4+1的段，这段的二进制表示的值等于这个word在2^{(r^4+1)i}这些位置的元素的和。

通过位移和\mathrm{AND}我们可以取出这个长r^4+1的段，于是就完成了。

答案即((((A-u'(S) \times C) \& C) \times (C \& (2^{(r^4+1)k}-1))) \& C)>>((k(r^4+1)-1)

O(1)计算rank(B(S),m)，m是在[0,w]中的整数：

由于我们可以O(1)计算rank(K(S),u'(S))，所以把这个查出来然后判断那一个数的大小，并且进行一次查表即可。

O(1)计算msb(u,v)：

等价于求u \;\mathrm{XOR}\; v的最高位1的位置，设A=u \;\mathrm{XOR}\; v。

我们将A分为r^c大小的块，总共r块，这里c是一个常数,c>1 令C=(100...0100...0......)_2，这里每两个1之间有r-1个1，C是一个常数。

注意到：

((100...0)_2-0)\&(1<<(r^c)-1)=(1<<(r^c)-1) ((100...0)_2-y)\&(1<<(r^c)-1)=0$，这里$y>0

先考虑对每个块去掉首位，块内是否有1。

我们用A\& \sim C可以去掉每一块的首位。

然后用C-(A\& \sim C)可以使得每一块中除首位外如果有1，则其在该块首位为0，否则为1。

然后用(C-(A\& \sim C))\&C去掉了C-(A\& \sim C)中每一块中除首位外的部分。

然后用(C-((C-(A\& \sim C))\&C))可以得到：如果一块中除首位外有1，则块首位为1，否则为0，且块首位外所有位置都是0的一个数 再考虑对每个块只保留首位，块内是否有1。

这个用A\&C即可。

最后(A\&C)|(C-((C-(A\& \sim C))\&C))可以得到：如果一块中有1，则块首位为1，否则为0，且块首位外所有位置都是0的一个数。

令D= \sum \limits _{k=0}^{r-1} 2^{k(r^c-1)}，

通过(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r)可以将每块首位的数字拼到一个长r的二进制数中。

然后我们可以使用前面的O(1)计算rank的方法，令B'(S)={2^i}，i在[0,r-1]间，是整数。

通过rank(B'(S),(((A\&C)|(C-((C-(A\& \sim C))\&C))) \times D)>>(w-r))就可以得到这个长r的二进制数中第一个非0的首位的位置了。

我们知道了第一个非0位在哪个块中，然后查这个块里面第一个非0位的位置就可以了。

由于我们每个块是r^c的大小，所以对一个大小为r^c，包含了2^i的集合用一次rank即找到了块内第一个非0的首位位置。

取c=4,r=w^{1/5}，r^c=w^{4/5}，我们便O(1)查询，O(w^{4/5})预处理时间复杂度解决了这个问题，由于预处理次数是O( n/B^4 )，所以这里也是线性的。

综上所述，我们得到了一个单次操作复杂度O( \log n/\log w + \log w )的数据结构，这里据说可以通过一些优化做到O( \log n/\log w )，但在这里由于我还没看所以暂时不做介绍。

6.一些拓展

如果我们允许下列中的一个：

1. 放松线性空间的限制

2. 保留线性空间的限制，但是使用随机化和整数除法

那么我们可以得到一个O( \sqrt{ \log n } )的动态搜索的时间复杂度上界。

当n超过2^{(\log w)^2/36}时（这里1/36的常数是论文中给出的，由于我的部分细节和论文中不同，可能是不同的常数），

对于1的case，可以通过使用vEB树来实现，对于2的case，可以通过使用Y-fast trie实现。

对于这样的n，这两个数据结构可以在O( \log \log U )=O( \log w )=O( \sqrt{\log n} )的时间完成一次搜索操作。

当n小于这个数时，

对于较小的n，我们使用fusion tree，通过调节B=Θ(2^ {\sqrt{\log n}})。

在这个B下，我们的时间复杂度是O( \log n/\log B + \log B ) = O( \sqrt{\log n} )。

综上所述，如果引入随机化和整数除法，可以O( n \sqrt{\log n} )时间，线性空间整数排序。

7.总结

由信息论可以证明基于比较的排序下界是\Omega( n\log n )的，但整数排序其实是非常复杂的一个问题，还有待研究。