nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

Y快速前缀树

继X快速前缀树以后，Dan Willard又提出了X快速前缀树的改进版本

改进X快速前缀树

我们还是继续考虑n个小于M的整数(n<M)，我们按照大小，从小到大分组,每组的元素的个数在区间\([\frac{lgM}{4},2lgM]\)上,对每组构建一颗普通平衡树，这样我们一共会得到\(\frac{n}{2lgM}\)到\(\frac{4n}{lgM}\)颗树，我们在这些树中取一个随便的值r，r要在平衡树的最大和最小值之间,这样我们每棵树对应了一个r，把所有的r作为键,其对应的平衡树作为值放到X快速平衡树中，这就是Y快速平衡树。

Y快速前缀树的查找前驱后继

首先在上层X前缀树上查找前驱和后继，最终我们会定位到两个叶子节点，也就对应了两颗普通平衡树，我们在这两颗普通平衡树里面直接找前驱后继然后合并就结束了。总复杂度\(lglg(\frac{n}{lgM})+2*lg(lgM)=lglgM\)

Y快速前缀树的插入

先在X前缀树上查询前驱后继，然后在其对应的平衡树上插入真正要插入的值，总复杂度\(lglg(\frac{n}{lgM})+lglgM=lglgM\)，这里有可能导致插入的值太多，进行分裂，我们来看一下这次分裂前插入了多少元素，我们考虑最坏的情况，不妨设之前也是分裂的，那么他的大小为\(lgM\)，到这次分裂一共插入了lgM+1个元素，导致现在的大小超过了2lgM，于是这lgM次插入的均摊分裂复杂度为\(\frac{lg(\frac{n}{lgM})}{lgM}\lt 1\),于是总复杂度为\(lglgM\)

Y快速前缀树的删除

同样的，我们还是先查询前驱后街，然后在对应的平衡树上删除真正要删除的值，总复杂度为\(lglg(\frac{n}{lgM})+lglgM=lglgM\),这里有可能导致平衡树上剩下的值太少，我们考虑合并，合并后如果依然太大，比方说大于lgM，我们就再次分裂为两个平衡树即可。这里可以证明，均摊复杂度依然是O1，因为从\(\frac{lgM}{2}\)到\(\frac{lgM}{4}\)也要\(\frac{lgM}{4}\)次删除，均摊下来，依然是O1,为了懒惰删除，我们甚至可以不必要求合并后超过lgM猜分裂，到2lgM也行。懒惰总是优秀的。于是总体复杂度为\(lglgM\)

总结

至此，Y快速前缀树的所有操作均为lglgM了.

代码

欠着欠着，以后再补。