本篇日志介绍第二种解法:(如果不喜欢这种解法,没关系!可以看后面的日志!)
Treap套函数式线段树
这是hzhwcmhf知道了解法一后提出的。
Treap的插入众所周知是期望O(logn)的,可是一个惊人的事实是,插入后旋转的期望次数是2次。旋转次数竟然是期望O(1)的!
假设s是以这个结点为根的子树的大小,如果你旋转一次耗费时间是O(s)的,那么插入后旋转的耗时竟然是期望O(logn)的!
非常惊人的结论!
所以Treap套函数式线段树就可捉了。
用Treap维护原序列,每个结点上带一个线段树维护以它为根的子树中出现的权值。
旋转的时候:
y x
/ \ / \
x c --------> a y
/ \ / \
a b b c
注意到子树a、b、c的线段树标记是不会变的,而x的线段树可以直接用原先y的线段树,y的线段树就暴力合并b、c的。
如果写的是函数式线段树,那么在旋转上的耗时就是O(logn)的。沿途插入是需要O(log^2n)的。
当然也可以直接不写函数式就写线段树,这样旋转上的耗时就是O(log^2n)的。
这样就解决了插入。
至于修改和查询,可以参考前一篇题解的修改和查询的做法,是一样的。
这份代码是hzhwcmhf根据我之前的替罪羊树那个代码改的。
评论