区间翻转后不满足左小右大，为什么能用此方法

P3391 【模板】文艺平衡树

BlankAo @ 2021-09-02 07:21:02

因为 Splay 满足左儿子小、右儿子大的性质，所以将 l-1 旋转到根， r+1 旋转到 l-1 的儿子，可以使得 r+1 的左儿子为区间 [l,r] 间的数字。

但是区间翻转后就不满足左小右大的性质了，为什么还能再使用以上的方法呢？

by LawrenceSivan @ 2021-09-02 07:35:51

@BlankAo 朋友，这是区间树，只需要满足中序遍历为原序列就可以了，并不是那种以权值为关键字的平衡树

by BlankAo @ 2021-09-02 07:36:02

先序遍历是中左右

by Echidna @ 2021-09-02 07:36:58

@DPair

中序遍历（LDR）是二叉树遍历的一种，也叫做中根遍历、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

来源：百度百科

by DPair @ 2021-09-02 07:38:15

我可能得重学遍历

by DPair @ 2021-09-02 07:38:30

好尴尬啊

by Echidna @ 2021-09-02 07:38:40

@DPair /jk

by BlankAo @ 2021-09-02 07:38:44

@LawrenceSivan 但是如何保证 r+1 的左子树刚好是 [l,r] 间

by DPair @ 2021-09-02 07:38:50

反正就这个意思（试图挽回颜面

by Leap_Frog @ 2021-09-02 07:40:02

@BlankAo 不是你 splay 打标记目标点你可以把它想象成拉出来的一棵子树，发现里面所有元素刚好是 [l,r]

by Echidna @ 2021-09-02 07:40:36

@BlankAo 你的根节点是 l-1 ，根节点的右儿子是 r+1 ，那么 r+1 的左子树不就必然是 [l,r] 了吗