在掌握了Splay树的基本查找功能之后，你可能会认为它与传统的二叉查找树没有太大差异，主要是通过splay操作减少了时间消耗。但Splay树被称为“序列之王”绝非偶然，其真正的优势在于高效的区间操作。
如何实现这些区间操作呢？
首先，我们知道二叉查找树的中序遍历结果是一个有序序列。在Splay树中，我们利用这一点，通过splay操作将需要操作的区间调整到特定位置，从而实现高效区间操作。
具体来说，Splay树支持以下几种操作：
1. 建树
2. 区间操作（如翻转、赋值等）
3. 输出序列
建树对于区间的构建，我们可以借鉴线段树的思想，采用递归的方式从中点开始构建。
void build(int& u, int l, int r, int fa) { if (l > r) return; u = ++siz; int mid = (l + r) >> 1; e[u].v = mid; e[u].siz = 1; e[u].f = fa; if (l + 1 这样递归地从中间开始建树，确保了树的平衡性。
区间操作 要对树中的某个区间进行操作，关键在于如何快速找到并调整这个区间。
Splay树的伸展操作（即splay操作）可以在不改变中序遍历顺序的前提下调整树的结构，这意味着我们可以在不改变序列的情况下改变树的形态。
例如，要操作区间 [l, r]，我们可以通过splay操作将 l-1 节点旋转到根节点，将 r+1 节点旋转到根节点的右子节点。此时，r+1 节点的左子树即为所需的区间 [l, r]。
如何找到这两个节点？可以使用splay中的查找第k个节点的方法。
对于操作整个区间 [1, N]，可以添加两个哨兵节点 0 和 N+1 来简化处理。
找到区间后，具体的区间操作（如翻转、赋值等）根据题目需求进行，通常会使用lazy标记来优化性能。
#define isr(x) (e[e[x].f].ch[1] == x) inline void spin(int u) { int fa = e[u].f, s = isr(u); e[u].f = e[fa].f; if (e[fa].f) e[e[fa].f].ch[isr(fa)] = u; e[fa].ch[s] = e[u].ch[s ^ 1]; e[fa].f = u; if (e[u].ch[s ^ 1]) e[e[u].ch[s ^ 1]].f = fa; e[u].ch[s ^ 1] = fa; up(fa); up(u); } void splay(int u, int fa = 0) { while (e[u].f != fa) { if (e[e[u].f].f && lazy[e[e[u].f].f]) pd(e[e[u].f].f); if (lazy[e[u].f]) pd(e[u].f); if (lazy[u]) pd(u); if (e[e[u].f].f == fa) spin(u); else if (isr(u) ^ isr(e[u].f)) spin(u), spin(u); else spin(e[u].f), spin(u); } if (!fa) root = u; }其中，lazy是标记数组，splay时需要传递标记，任何涉及子节点的操作都应考虑标记的传递。
输出序列 输出序列实际上就是进行中序遍历，具体实现可以自行编写。
示例题目 一个典型的区间操作题目是洛谷P3391 文艺平衡树，主要涉及区间翻转。
#include #include #include #define isr(x) (e[e[x].f].ch[1] == x) using namespace std; const int maxn = 200005, INF = 2000000000; int N, M; inline int read() { int out = 0, flag = 1; char c = getchar(); while (c <48 || c > 57) { if (c == '-') flag = -1; c = getchar(); } while (c >= 48 && c <= 57) { out = out * 10 + c - 48; c = getchar(); } return out * flag; } int lazy[maxn]; class node { public: int v, ch[2], f, siz; node() { ch[0] = ch[1] = 0; siz = 0; } }; node e[maxn]; int siz = 0, root = 0; inline void up(int u) { e[u].siz = e[e[u].ch[0]].siz + e[e[u].ch[1]].siz + 1; } inline void pd(int u) { swap(e[u].ch[0], e[u].ch[1]); lazy[e[u].ch[0]] ^= 1; lazy[e[u].ch[1]] ^= 1; lazy[u] ^= 1; } inline void spin(int u) { int fa = e[u].f, s = isr(u); e[u].f = e[fa].f; if (e[fa].f) e[e[fa].f].ch[isr(fa)] = u; e[fa].ch[s] = e[u].ch[s ^ 1]; e[fa].f = u; if (e[u].ch[s ^ 1]) e[e[u].ch[s ^ 1]].f = fa; e[u].ch[s ^ 1] = fa; up(fa); up(u); } void splay(int u, int fa = 0) { while (e[u].f != fa) { if (e[e[u].f].f && lazy[e[e[u].f].f]) pd(e[e[u].f].f); if (lazy[e[u].f]) pd(e[u].f); if (lazy[u]) pd(u); if (e[e[u].f].f == fa) spin(u); else if (isr(u) ^ isr(e[u].f)) spin(u), spin(u); else spin(e[u].f), spin(u); } if (!fa) root = u; } int kth(int u, int k) { if (lazy[u]) pd(u); if (k == e[e[u].ch[0]].siz + 1) return u; else if (k > e[e[u].ch[0]].siz + 1) return kth(e[u].ch[1], k - e[e[u].ch[0]].siz - 1); return kth(e[u].ch[0], k); } void change(int l, int r) { int L = kth(root, l), R = kth(root, r + 2); splay(L); splay(R, root); lazy[e[e[root].ch[1]].ch[0]] ^= 1; } void build(int& u, int l, int r, int fa) { if (l > r) return; u = ++siz; int mid = (l + r) >> 1; e[u].v = mid; e[u].siz = 1; e[u].f = fa; if (l + 1 = 1 && e[u].v <= N) printf("%d ", e[u].v); print(e[u].ch[1]); } } int main() { N = read(); M = read(); int a, b; build(root, 0, N + 2, 0); while (M--) { a = read(); b = read(); if (a == b) continue; change(a, b); } print(root); cout < 
京公网安备 11010802041100号