热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Splay树的高级应用:区间操作详解

在学习了Splay树的基本查找功能后,可能会觉得它与普通的二叉查找树没有太大的区别,仅仅是通过splay操作减少了时间开销。然而,Splay树之所以被誉为“序列之王”,主要在于其强大的区间操作能力。

在掌握了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 <

推荐阅读
author-avatar
会丶有那么一天
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有