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

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

by BlankAo @ 2021-09-02 07:42:46

@某学oi的蒟蒻 但就算平衡树的权值是原数列的下表，区间翻转后也不能保证左小右大吧

by LawrenceSivan @ 2021-09-02 07:43:55

@BlankAo 我似乎听不太明白你的意思/jk

by BlankAo @ 2021-09-02 07:45:18

@LawrenceSivan 啊就是怎么样找到区间 [l,r]

by DPair @ 2021-09-02 07:45:28

@BlankAo 你可以这么理解

他并不是原下标左小右大，而是节点的 中序遍历后的下标 由于平衡树的性质变得左小右大

你可以考虑这段区间前后都没有变化，而这段区间内的所有点都发生了 下标的变化

by Echidna @ 2021-09-02 07:46:20

@BlankAo 假如说题目给了你一个操作，要求把 [l,r] 翻转，那么不就相当于把 [l,r] 的所有的数的下标反标了吗

所以说你只需要对应在平衡树里把 [l,r] 这颗子树找出来，然后把其中所有节点都交换左右儿子就好了

但是这样时间复杂度太高了，我们无法接受，并且这个操作也不需要立即完成。所以我们就把这个操作用懒标记的方式实现，这样体现在代码里就是交换左右儿子并且给左右儿子打上懒标记。

by DPair @ 2021-09-02 07:46:56

普通平衡树是按照当前节点的权值来的，这里你多维护一个 size 表示当前节点子树大小

然后你用类似二分的方法就可以找到中序遍历后为 [l, r] 的区间了

我相信这题题解里有写

by Echidna @ 2021-09-02 07:48:14

啊就是怎么样找到区间 [l,r]

@BlankAo 您直接把这棵树中第 l-1 大的元素旋转到高度为 0 的位置，把第 r+1 大的元素旋转到高度为 1 的位置，那 r+1 的左儿子的子树不就是 [l,r] 吗？/yiw

by BlankAo @ 2021-09-02 07:50:22

明白了，十分感谢！！！ @DPair @某学oi的蒟蒻 @LawrenceSivan

by LawrenceSivan @ 2021-09-02 07:50:44

@BlankAo 由于在旋转过程中， Splay 并不会改变中序遍历为原序列的性质，所以可以知道 r+1 的位置一定是在 r 后面的，所以对应在二叉树上他的中序遍历一定在 r 的后面。根据中序遍历的性质一个点之前的点一定在左子树中，同理可以得到 l