Splay 之区间操作

Splay 维护区间操作

Posted by TH911 on August 25, 2025

例题链接

您需要写一种数据结构(可参考题目标题),来维护一个有序数列。

其中需要提供以下操作:翻转一个区间,例如原有有序序列是 $5\ 4\ 3\ 2\ 1$,翻转区间是 $[2,4]$ 的话,结果是 $5\ 2\ 3\ 4\ 1$。

前置知识:Splay

参见Splay 树详解

平衡树维护区间信息

无论是 Splay 还是 FHQ Treap,亦或是其他平衡树,维护区间信息的本质都是——一棵子树代表一段区间