一、Splay

参考文档 OIWIKI Splay 树

例1. P3369 【模板】普通平衡树

【参考代码】Splay

例2. P3391 【模板】文艺平衡树

【分析】以位置为值插入到 Splay 中，为了避免越界，多插入两个节点 $0$ 和 $n+1$.

对于区间 $[l,r]$ 旋转（实际需要平移查询 $[l+1,r+1]$，后续为了好理解，直接使用 l,r），按位置查找到 $l-1$ ，将其 Splay 到根，在根节点 root 右子树里面，按位置找到 $r-l+2$ 的点 (即对应 $r+1$ 处的点) , 那么 ch[root][1] 的左儿子 ch[ch[root][1]][0] 就对应区间翻转区间。使用懒标记整个子树，也就是将一个区间对应一颗子树。

【参考代码】Splay 区间翻转 模板

二、Splay 时间复杂度证明

OIwiki 上写的有点抽象，于是我写的简单易懂一点。

参考教程：

• 【教程】均摊复杂度

• 【教程】势能分析法 与 Splay 时间复杂度证明

学习完毕

{{ select(1) }}

• YES
• NO