主讲人：李欣隆
D1:
Treap(tree+heap)性质:每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质，复杂度 \(O(n\log n)\)。
旋转(rotate)有单旋和双旋, treap只需要单旋，这一点比较简单。
旋转时最好先记录每个点的编号，再断连，再重构，最后按照点的编号调用函数 update(x)。
Splay:每次对一个节点进行操作的时候通过―种方法把这个点旋转至根，称为Splay（伸展）操作
2023-12-05 14:18:52
Treap(tree+heap)性质:每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质，复杂度 \(O(n\log n)\)。
旋转(rotate)有单旋和双旋, treap只需要单旋，这一点比较简单。
旋转时最好先记录每个点的编号，再断连，再重构，最后按照点的编号调用函数 update(x)。
Splay:每次对一个节点进行操作的时候通过―种方法把这个点旋转至根，称为Splay（伸展）操作