Splay?线段树?Splay线段树!

小柯

2020-04-22 22:09:07

Personal

$xk$那时正在学习树剖,为了不被大佬吊打得太惨,所以去学习了$LCT$可是却发现自己连$Splay$都不会,于是把目光投向了$Splay$(嘿嘿嘿),可是看了半天都看不懂,于是冒着被吊打的风险去向大佬请教(结果果然被吊打了),才学会了$Splay$,那时恰好刚刚学完线段树没多久,于是$xk$产生了一个把这两个数据结构结合的想法,可是想到线段树应该不能像$BST$那样旋转,于是放弃了...... ...... 只到上次开学考试已经开始放弃治疗的时候,为了消磨时间,$xk$再次想起了这个玩意儿。这次,他已经对$Splay$有一定了解了,于是他改变了思路,决定从$Splay$出发魔改。他记得权值线段树可以做到像平衡树一样的效果,于是他决定尝试以下标为第一关键字,维护一颗$Splay$,同时每个节点维护其子树数字和。