有没有FHQTreap实现LCT的博客 (最好有板子)

回复帖子

@142857cs 2019-03-15 14:02 回复

这个好像复杂度不能证明是1个log

@longlongzhu123 2019-03-15 14:05 回复

@142857cs 的确是两个log,access一个,split和merge各一个

Splay中一个Rotate也是一个log的(对势能贡献),只不过因为一些玄学原因均摊起来变成了logn

LCT原理类似,一堆Splay加起来均摊一个log

@142857cs 2019-03-15 14:05 回复

可以用某个奇怪的平衡树做到1个log,不过应该没有人会去写。。。