若干丧心病狂的平衡树

最近翻 paper，偶然看到了 O(log log N) 的堆，有些兴趣于是乎研究起来，依稀记得 fhq 在冬令营有讲过， 但是由于当时开小差所以没听懂，不过事后翻了翻当时的 ppt 也没太看懂。

基于比较的排序已经是被证明复杂度不低于 O(NlogN) ，因此，基于比较的堆也不可能做到均摊 logN ，所以这些堆都有它的特殊性， 就是权值范围固定，比如权值范围为 D，则复杂度为 O(log log D)，当然，后面提到的这两种数据结构都不仅仅是一个堆，他们还可以找 lower_bound，复杂度同样是 O(loglogN)。

Google 了一番，首先找到了这么一篇论文 A Priority Queue in Which Initialization and Queue Operations Take O(loglogD) Time， 大概的思路是在在二叉树上二分，当然，这棵二叉树是静态的，底部有 2^n 个节点，一共 n+1 层，看了许久还拉上 lyp 看才差不多知道是个怎么回事， 但是对于实现还是一无所知……遂放弃这种方法……

之后通过各种 Google，又找到这么一种数据结构，名曰 Van Emde Boas trees，有一篇中文 Blog 讲的很好，传送门，文中说算导里有介绍这个数据结构， 为啥我的算导上没有…

简单的来说就是这样一个数据结构，假设一个大小为 N 的 veb树，那么他会有 sqrt(N) 个分支，每个分支都是一颗 veb树， 而为了维护这 sqrt(N) 个分支，专门在额外用一颗 veb树（假设命名为 summary ）来管理这 sqrt(N) 个分支。

当然这么做还不够，一次插入岂不是既要在 summary 中插入又要在子树中插入，这样两次插入造成复杂度退化为 O(logN)，于是乎通过维护一个类似于 lazy 标记的最小值就可以做到每次只会产生一次新的递归调用，因为每次树的规模都是直接开根号，所以复杂度为 O(loglogN)。

还算是个比较优美的算法，而且常数似乎不大，怒实现了一发。

但是不幸的是，做了下测试，这货和 treap 差不多…