关于treap的两个问题

1、启发式合并的均摊复杂度是多少？以及怎么算的……是要基于一定条件下才能只有一个n吧
2、treap怎么支持序列操作（区间翻转、移动）……完全没懂fhq那篇文章

觉得还算好懂啊……
首先你要明白，范浩强treap不是以前的那种treap。
然后去仔细看看Split和merge函数就行了
有了这两个函数就能处理区间问题了

不感兴趣

开通SVIP免广告

1：nlognlogn，因为插入是logn的【不过据说splay是nlogn
2：太神不会【我只会splayTUT

1，Splay 才能实现 nlogn 启发式合并。具体可以参见 wiki 里的 splay tree。
2，treap实现这些的方法主要是如何 logn 内完成把一个 treap 切成大小为 k, n - k，logn 内完成两个 treap 的合并。实现可以看 fhq blog。

我弱仍然没懂……有人能帮忙讲讲为何treap启发式合并的插入为n log n次吗？

LZ你在3楼回复举的那个例子不对你那叫做合并不叫做启发式合并你举的那个例子是我可以随便挑选两棵treap合并但往往我们使用启发式合并是因为被提前规定好了合并顺序不是一直都在往一棵树上合并也就是说我第一次合并的是1和2 第二次可以合并3和4 那么考虑复杂度由于我们的启发式合并是把小树合并到大树中那么合并之后的树的size至少是小树的两倍所以任何一棵树加入到其他树中的次数至多为logn 树的个数是O(n)的所以插入的次数是O(nlogn)的

扫二维码下载贴吧客户端

下载贴吧APP
看高清直播、视频！

20回复贴，共1页

<<返回noip吧

分享到:

日	一	二	三	四	五	六