题目背景
题目背景和题意无关,可以跳过
1.前言:
Fusion Tree,中文译作融合树,是一种亚log的数据结构,与1993年由Michael L.Fredman和Dan E.Willard提出。
用途:O(logn/logw+logw)时间复杂度支持插入,删除,前驱,后继,min,max,以及用于整数排序。
信息论断言对n个数的排序在最坏情况下需要nlogn次比较,不过对这个界我们还需要一些研究。
有人证明了任意unit cost RAM算法,其中只包含加法,减法,乘法,和0比较(但是不包含除法和位运算)最坏情况下需要Ω(nlogn)的时间去对n个数排序。
如果允许使用除法和位运算,他们有一个线性时间复杂度的算法,但是这个算法对unit cost滥用。
这里我们规定我们使用的计算模型的字长是w,每个输入的数都是在[0,2w−1]中的整数。
2.一些记号:
对于一个集合S和一个整数x,定义rank(S,x)为S集合中≤x的元素个数。 对于一些非负整数a,定义bin(a1,...,an)=2ai+...+2an。
对于两个非负整数a,b,定义msb(u,v)为u和v最高的不相同的位。
3.概述:
Fusion Tree大概可以看做是一棵特殊的B-Tree,特性:
叉数B=O(w1/5)
在一次搜索时,每个在搜索路径上的节点的正确的儿子可以被O(1)确定
从这些特性我们可以看出Fusion Tree单次操作的时间复杂度是O(logw(n)+logw)=O(logn/logw+logw)的,比O(logn)低。
但是由于其实现方式,Fusion Tree每次对内部节点的更新复杂度是O(B4)的。 为了控制Fusion Tree均摊的更新复杂度,我们将这棵B-Tree的每对叶子节点之间的部分替换为一个大小大约为O(B4)的Weight Balanced Tree,只在WBT根节点发生变化的时候更新Fusion Tree的内部节点。
具体来说,我们B-Tree维护的是一个排序后的数组的分块,其中每个块都由一棵平衡二叉搜索树维护,fusion tree上只维护一个值来表示块边界,用途是指引每次插入,删除,查询在哪个块中。
可以发现这样我们把内部节点的变化次数除掉了一个B4。
4.压缩key的表示:
如何O(1)确定搜索路径上的一个节点的正确的儿子:
考虑一个B-Tree的节点,其上面包含了k个key,其中B/2≤k≤B,记作S=u1,u2,...uk。
然后我们定义出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)排序后为c1<c2<⋯<cr,定义边界c0=−1,cr+1=b。
定义u′i为K(S)中任意的一个压缩后的key。
对于一个任意的w−bit的数u,满足u≠ui,
设msb(u′(S),u′i)=cm,即u和ui在bit位置cm+1,...,cr位置处相等,但是在cm处不相等,如果u′(S)=u′i,则我们记m=0。
如果u和ui不同的最高位p满足p>cm,那么我们可以通过:
唯一的一个区间[cj−1,cj]满足p属于这个区间
u和ui的大小关系
来确定rank(S,u)的值。
证明平凡,把trie画出来,显然可以画成一个平面图,然后可以发现这两个可以唯一地确定出一个平面区域,这个区域中的S集合元素个数就是rank(S,u)(感觉这种东西光写一堆自然语言也不能说明正确性,需要形式化证明一下?)。
注意到这个引理虽然是对任意ui成立的,但是要求u和ui不相同的最高位不是B(S)中的一个点,可以发现这个ui其实必须在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(这两个值不一定存在,但经过平凡的讨论就可以解决。
如果uj≤u≤uj+1,那我们已经解决了这个问题 否则我们令i=j或者i=j+1,计算出msb(ui,u)=p,然后只要我们知道了包含p的区间[cj,cj+1],我们就可以通过引理1来确定出rank(S,u)的值。
这里如果我们uj≤u≤uj+1,那我们已经达成了目的,不用继续考虑了。
否则如果不满足uj≤u≤uj+1,也就是说我们在这个sketch的过程中丢失了信息,即说明保留K(S)这些位的信息是不够的,那么p一定不在K(S)中,也就是说i=j和i=j+1中p较小的i满足p>cm,故可以使用引理1。
计算K(S)和u′(S): 我们发现没有平凡的方法可以将一个w−bit的数u在O(1)时间把B(S)那些位提取出来之后放到连续的一段中(可能可以通过硬件支持实现?),即使经过了一定预处理。
其实我们不需要做到这个,可以用具有:
将需要提取出的位提取出,并放到(可以不连续)的更短的一段中
保序性
的其他变化来实现我们需要的效果。
我们可以通过一次恰当的乘法和一次与运算来实现这个:
沿用引理1的定义,设我们需要从u中提取这些位,令C=bin(c1,...,cr)。
假设我们已经算出了C,我们先通过令v=uANDC来将u中不需要的那些位置0。
然后我们将v乘以一个量M,从而把v中我们需要的那些bit转化到一个狭窄的范围内,然后再通过一次AND来清除掉不需要的位置 这里给出对一个量M的存在性证明和构造:
记M=bin(m1,...,mr),如果我们暂时忽略交叉和进位造成的影响,那么可以认为v乘M是把c1,...cr这些位置的位重新定位到了。
c1+m1,...,cr+mr上。
如果对任意1≤i,j≤r,这r2个ci+mj都是不同的,那么就不会发生交叉和进位了。
我们现在的目标是构造一个整数集合m1,...,mr,使得:
c1+m1<c2+m2<⋯<cr+mr
对任意1≤i,j≤r,ci+mj都是两两不同的。
变换后的区间[c1+m1,cr+mr]"相对较小",这里的相对较小其实只要是O(poly(r))的即可,因为这样我们可以通过调整树的叉数来满足后续的条件。
引理2:
给一个r个整数的序列,c1<...<cr,存在一个r个整数的序列,m1,...mr,满足:
c1+m1<c2+m2<...<cr+mr
对任意1≤i,j≤r,ci+mj都是两两不同的。
(cr+mr)−(c1+m1)≤r4
证明:
先考虑证明存在整数序列m′1,...,m′r,使得对任意i,j,a,b,m′i+ca与m′j+cb在模r3的意义下不同余。
如果我们找到了这样的整数序列,那么所有r2个ci+m′j都是两两不同的,并且由于这个是在模r3意义下两两不同的,所以我们可以对第i个ci+m′i加上(i−1)⋅r3,这样就可以保证对所有i满足ci+m′i<ci+1+m′i+1了。
关于m′1,...,m′r的存在性:
使用数学归纳法来证明,显然我们可以找到m′1,这个平凡。
假设结论对t成立,即我们已经找到了m′1,...,m′t,满足对任意1≤i,j≤t,a,b,有m′i+ca与m′j+cb在模r3的意义下不同余。 可以观察到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 \cdot 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 )空间的。
下面给出对
- rank(K(S),u'(S))
- rank(B(S),m),其中m是在[0,w]中的整数
- 两个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.一些拓展
如果我们允许下列中的一个:
放松线性空间的限制
保留线性空间的限制,但是使用随机化和整数除法
那么我们可以得到一个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 )的,但整数排序其实是非常复杂的一个问题,还有待研究。
题目描述
魔法森林里有一颗大树,下面经常有小孩召开法。
大树可以看做一个有 n 个节点,n - 1 条边的无向连通图。大树的每个节点都有若干瓶矿泉水,初始第 i 个节点有 a_i 瓶矿泉水。
麦杰斯住在大树顶端,有一天他想改造一下大树,方便他巨大多喝水之后可以垃圾分类矿泉水瓶。
麦杰斯喜欢二进制运算,所以他会有以下三种操作:
- 将树上与一个节点 x 距离为 1 的节点上的矿泉水数量 +1。这里树上两点间的距离定义为从一点出发到另外一点的最短路径上边的条数。
- 在一个节点 x 上喝掉 v 瓶水。
- 询问树上与一个节点 x 距离为 1 的所有节点上的矿泉水数量的异或和。
麦杰斯共有 m 次操作,他希望你在每次 3 操作后告诉他答案。
输入格式
第一行两个正整数 n,m,分别表示树的节点个数和麦杰斯的询问个数。
第二行到第 n 行,每行两个整数表示有一条连接这两个节点的边。
第 n + 1 行 n 个整数,第 i 个整数表示初始第 i 个节点上的矿泉水数量。
第 n + 2 行到第 n + m + 1 行,每行先读入一个整数 opt 表示操作类型。
如果 opt = 1 或 3 ,接下来读入一个整数 x 表示麦杰斯操作的节点标号。
否则接下来读入两个整数 x, v 表示麦杰斯操作的节点标号和他喝的水的数量。
输出格式
对于每一个 3 操作,输出一行一个整数表示答案。
样例数据
样例输入
3 2
1 2
2 3
1 1 4
1 1
3 2
样例输出
5
子任务
Idea:dangxingyu,Solution:dangxingyu,Code:dangxingyu,Data:dangxingyu
对于 30\% 的数据,满足 n \le 10^3,m\le 10^3。
对于 60\% 的数据,满足 n \le 10^5,m \le 10^5。
对于另外 10\% 的数据,存在一个点满足所有点到该节点的距离 \le 1。
对于 100\% 的数据,满足 1\le n \le 5\times 10^5,1\le m \le 5\times 10^5,0\le a_i \le 10^5,1 \le x \le n,opt\in\{1,2,3\}。
保证任意时刻每个节点的矿泉水数非负。
温馨提示:矿泉水瓶不是干垃圾也不是湿垃圾,而是可回收垃圾。