首页 > 其他分享 >FHQ-Treap的详细图解

FHQ-Treap的详细图解

时间：2023-07-12 17:35:22浏览次数：48  
标签：idx int root tr Treap key 图解 FHQ size

第一部分 按值分裂的 FHQ-Treap

按值分裂的 FHQ-Treap 的典型例题是P3369 【模板】普通平衡树。

思路

FHQ-Treap 是什么？

FHQ-Treap 是二叉搜索树的一种。

比如：

image

FHQ-Treap 的思想是什么？

分裂->操作->合并

下面我们就来慢慢讲这些操作。

分裂

我们可以根据给定的 \(k\) 将平衡树分成两个部分，一部分节点的值都小于等于 \(k\)，一部分节点的值都大于 \(k\)。

比如 \(k = 10\) 时我们把上图分成这样两个部分：

image

即：

image

左边的 \(2, 3, 4, 5, 6, 7, 9, 10\) 都小于等于 \(10\)，右边的 \(12, 15, 18\) 都大于 \(10\)。

那么，怎么让计算机实现呢？

我们发现图中的 \(9, 10\) 本不相连，但在分裂后却是相连的，所以我们并不能讨论是否只断掉某条边就可以实现分裂。

分裂的过程实际上是在找这个点的过程中完成的：

image

下面我们以分裂出 \(\leq k\) 这部分为例讲讲怎么实现分裂。

首先我们发现，当遍历到一个节点 \(u\)，如果 \(u\) 的值小于等于 \(k\)，我们容易根据二叉搜索树的性质得出结论：\(u\) 所有的左子树的值 \(\leq k\)：

image

\(u\) 的右子树的值都不小于 \(u\) 的值，也有可能有 \(\leq k\) 的部分，我们也要把它们（当然也有可能是）连起来。

因为 \(u\) 的右子树任何一个数值都比 \(u\) 的数值要大，所以从 \(u\) 连向任何右边的点都是合法的：

image

所以当我们在遍历右子树的某个点 \(d\) 的时候，如果又出现了 \(d\) 的值 \(\leq k\)，那么就可以把 \(u\) 的连接右子树的边连到 \(d\) 上：

image

还有一个比较特殊的点，它没有父节点，那么它就作为根。

以上是处理 \(\leq k\) 的部分的思想，处理 \(> k\) 的方法类似，反着来就行了。

合并

FHQ-Treap 和 普通 Treap 一样，也分优先级，维护一个堆的性质。

采用上小下大或上大下小都可以。

合并比分裂容易得多，谁的优先级高，谁就先上。

插入

分裂：假如要插入 \(k\)，将平衡树拆分成 \(\leq k\) 和 \(>k\) 两部分；

新建节点：再新建一个节点，值为 \(k\)；

合并：先合并 \(\leq k\) 的部分和新建节点，然后再与 \(>k\) 的部分合并。

image

删除

分裂：假如要删除 \(k\)，将平衡树分成 \(<k, =k, >k\) 三个部分。

合并：最后将 \(=k\) 的那个部分的左右子树合并，再把这三个部分合并就可以了。

查询一个数的排名

分裂：将平衡树分裂成 \(\leq (k - 1)\) 和 \(>(k - 1)\) 的两个部分。

结果：排名就是 \(\leq (k - 1)\) 这一子树的大小 \(+1\)。

合并：将分裂出来的两个部分合并。

使用排名来查找数字

设当前遍历到点 \(u\)。

  1. 如果 \(u\) 的左子树的大小 \(+1\) 等于排名，那么结果就是 \(u\) 这个节点的数字；
  2. 如果 \(u\) 的左子树大小大于等于排名，说明结果在左子树中，那么递归查询左子树；
  3. 否则遍历 \(u\) 的右子树，注意，查询右子树时记得将排名减去 \((左子树的大小 + 1)\)。

找 \(x\) 的前驱

分裂：将平衡树分成 \(\leq (x - 1)\) 和 \(>(x - 1)\) 的两个部分

结果：使用上面的“使用排名来查找数字”的方法求出 \(\leq (x - 1)\) 部分的平衡树的最大的一个数。

合并：将分裂出来的两个部分合并。

找 \(x\) 的后继

分裂：将平衡树分成 \(\leq x\) 和 \(>x\) 的两个部分

结果：使用上面的“使用排名来查找数字”的方法求出 \(>x\) 部分的平衡树的最小的一个数。

合并：将分裂出来的两个部分合并。

例题代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct node {
	int l, r;
	int size;
	int rnd;
	int key;
} tr[N];

int root, idx;

void pushup(int u) {
	tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}

int newnode(int key) {
	idx++;
	tr[idx].key = key;
	tr[idx].rnd = rand();
	tr[idx].size = 1;
	tr[idx].l = tr[idx].r = 0;
	return idx;
}

void split(int u, int key, int &x, int &y) {
	if (!u) {
		x = y = 0;
		return;
	}
	if (tr[u].key <= key) {
		x = u;
		split(tr[u].r, key, tr[u].r, y);
	}
	else {
		y = u;
		split(tr[u].l, key, x, tr[u].l);
	}
	pushup(u);
}

int merge(int x, int y) {
	if ((!x) || (!y)) return x | y;
	if (tr[x].rnd < tr[y].rnd) {
		tr[x].r = merge(tr[x].r, y);
		pushup(x);
		return x;
	} 
	else {
		tr[y].l = merge(x, tr[y].l);
		pushup(y);
		return y;
	}
}

void insert(int key) {
	int x, y, z;
	split(root, key, x, y);
	z = newnode(key);
	root = merge(merge(x, z), y);
}

void del(int key) {
	int x, y, z;
	split(root, key, x, y);
	split(x, key - 1, x, z);
	z = merge(tr[z].l, tr[z].r);
	root = merge(merge(x, z), y);
}

int get_rank_by_key(int key) {
	int x, y, z;
	split(root, key - 1, x, y);
	int ans = tr[x].size + 1;
	root = merge(x, y);
	return ans;
}

int get_key_by_rank(int u, int rk) {
	if (tr[tr[u].l].size + 1 == rk) return tr[u].key;
	else if (tr[tr[u].l].size >= rk) return get_key_by_rank(tr[u].l, rk);
	else return get_key_by_rank(tr[u].r, rk - tr[tr[u].l].size - 1);
}

int get_pre(int key) {
	int x, y, z;
	split(root, key - 1, x, y);
	int ans = get_key_by_rank(x, tr[x].size);
	root = merge(x, y);
	return ans;
}

int get_nxt(int key) {
	int x, y, z;
	split(root, key, x, y);
	int ans = get_key_by_rank(y, 1);
	root = merge(x, y);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	int opt, x;
	while (T--) {
		cin >> opt >> x;
		if (opt == 1) insert(x);
		else if (opt == 2) del(x);
		else if (opt == 3) cout << get_rank_by_key(x) << '\n';
		else if (opt == 4) cout << get_key_by_rank(root, x) << '\n';
		else if (opt == 5) cout << get_pre(x) << '\n';
		else cout << get_nxt(x) << '\n';
	}
	return 0;
}

第二部分 按大小（\(size\)）分裂的 FHQ-Treap

按大小分裂的 FHQ-Treap 的典型例题是P3391 【模板】文艺平衡树。

思路

在所有操作中，除了分裂操作以外，都是一样的。

只有分裂操作与按值分裂的不同，比较的对象是大小：

原图：

image

操作：

image

结果：

image

例题代码

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

struct node {
    int l, r;
    int sz;
    int key;
    int rnd;
    int tag;
} tr[N];

int root, idx;

void pushup(int u) {
    tr[u].sz = tr[tr[u].l].sz + tr[tr[u].r].sz + 1;
}

int newnode(int key) {
    idx++;
    tr[idx].key = key;
    tr[idx].rnd = rand();
    tr[idx].tag = 0;
    tr[idx].l = tr[idx].r = 0;
    tr[idx].sz = 1;
    return idx;
}

void pushdown(int u) {
    if (tr[u].tag) {
        tr[tr[u].l].tag ^= 1;
        tr[tr[u].r].tag ^= 1;
        swap(tr[u].l, tr[u].r);
        tr[u].tag = 0;
    }
}

void split(int u, int sz, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }
    pushdown(u);
    if (tr[tr[u].l].sz + 1 <= sz) {
        x = u;
        split(tr[u].r, sz - tr[tr[u].l].sz - 1, tr[u].r, y);
    }
    else {
        y = u;
        split(tr[u].l, sz, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if ((!x) || (!y)) return x | y;
    if (tr[x].rnd > tr[y].rnd) {
        pushdown(x);
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else {
        pushdown(y);
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

void insert(int p, int key) {
    int x, y, z;
    split(root, p - 1, x, y);
    z = newnode(key);
    root = merge(merge(x, z), y);
}

void reverse_arr(int l, int r) {
    int x, y, z;
    split(root, r, x, z);
    split(x, l - 1, x, y);
    tr[y].tag ^= 1;
    root = merge(merge(x, y), z);
}

void dfs(int u) {
    if (!u) return;
    pushdown(u);
    dfs(tr[u].l);
    cout << tr[u].key << ' ';
    dfs(tr[u].r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, T;
    cin >> n >> T;
    for (int i = 1; i <= n; i++) insert(i, i);
    while (T--) {
        int l, r;
        cin >> l >> r;
        reverse_arr(l, r);
    }

    dfs(root);

    return 0;
}

第三部分 练习

P4008 [NOI2003] 文本编辑器

题目描述

image

思路

文艺平衡树的基本运用。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3200000;

struct node {
    int l, r;
    int size;
    char key;
    int rnd;
} tr[N];

int root, idx;

int newnode(char key) {
    idx++;
    tr[idx].key = key;
    tr[idx].rnd = rand();
    tr[idx].size = 1;
    tr[idx].l = tr[idx].r = 0;
    return idx;
}

void pushup(int u) {
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}

void split(int u, int sz, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }
    if (tr[tr[u].l].size + 1 <= sz) {
        x = u;
        split(tr[u].r, sz - tr[tr[u].l].size - 1, tr[u].r, y);
    }
    else {
        y = u;
        split(tr[u].l, sz, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if ((!x) || (!y)) return x | y;
    if (tr[x].rnd < tr[y].rnd) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

int p;

void insert(int sz) {
    int x, y, z = 0, s;
    split(root, p, x, y);
    char ch = 0;
    for (int i = 1; i <= sz; i++) {
        ch = getchar();
        if (ch == '\n' || ch == '\r') {
            i--;
            continue;
        }
        s = newnode(ch);
        if (!z) z = s;
        else z = merge(z, s);
    }
    root = merge(merge(x, z), y);
}

void del(int sz) {
    int x, y, z;
    if (!p) {
        split(root, sz, x, y);
        root = y;
        return;
    }
    split(root, p + sz, x, z);
    split(x, p, x, y);
    root = merge(x, z);
}

void output(int u) {
    if (!u) return;
    output(tr[u].l);
    putchar(tr[u].key);
    output(tr[u].r);
}

void print(int sz) {
    int x, y, z;
    split(root, p + sz, x, z);
    split(x, p, x, y);
    output(y);
    root = merge(merge(x, y), z);
    putchar('\n');
}

int main() {
    int T;
    char opt[10];
    scanf("%d", &T);

    while (T--) {
        scanf("%s", opt);
        if (opt[0] == 'M') scanf("%d", &p);
        else if (opt[0] == 'I') {
            int sz;
            scanf("%d", &sz);
            insert(sz);
        }
        else if (opt[0] == 'D') {
            int sz;
            scanf("%d", &sz);
            del(sz);
        }
        else if (opt[0] == 'G') {
            int sz;
            scanf("%d", &sz);
            print(sz);
        }
        else if (opt[0] == 'P') p--;
        else p++;
        // output(root);
        // cout << endl;
    }
    return 0;
}

P2596 [ZJOI2006] 书架

题目描述

image

思路

对每一种操作，

对 FHQ-Treap 树按要求进行分裂，

再用不同的顺序进行合并，

就实现了题目中的各种调换。

是练习分裂的绝佳好题。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 90010;

struct node {
    int l, r;
    int size;
    int key;
    int rnd;
    int fa;
} tr[N];

int root, idx;
int st[N];

int newnode(int key, int fa) {
    idx++;
    st[key] = idx;
    tr[idx].key = key;
    tr[idx].fa = fa;
    tr[idx].rnd = rand();
    tr[idx].size = 1;
    tr[idx].l = tr[idx].r = 0;
    return idx;
}

void pushup(int u) {
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
    if (tr[u].l) tr[tr[u].l].fa = u;
    if (tr[u].r) tr[tr[u].r].fa = u;
}

void split(int u, int sz, int &x, int &y) {
    if (!u) {
        x = y = 0;
        return;
    }
    if (tr[tr[u].l].size + 1 <= sz) {
        x = u;
        split(tr[u].r, sz - tr[tr[u].l].size - 1, tr[u].r, y);
    }
    else {
        y = u;
        split(tr[u].l, sz, x, tr[u].l);
    }
    pushup(u);
}

int merge(int x, int y) {
    if ((!x) || (!y)) return x | y;
    if (tr[x].rnd < tr[y].rnd) {
        tr[x].r = merge(tr[x].r, y);
        pushup(x);
        return x;
    }
    else {
        tr[y].l = merge(x, tr[y].l);
        pushup(y);
        return y;
    }
}

int get_rank(int ver, int rt) {
    int rk = tr[tr[ver].l].size;
    while (ver != rt) {
        int fa = tr[ver].fa;
        if (tr[fa].r == ver) rk += tr[tr[fa].l].size + 1;
        ver = fa;
    }
    return rk + 1;
}

void insert(int p, int key) {
    int x, y, z;
    split(root, p - 1, x, y);
    z = newnode(key, 0);
    root = merge(merge(x, z), y);
}

void top(int s) {
    int p = get_rank(st[s], root);
    int x, y, z;
    split(root, p, x, z);
    split(x, p - 1, x, y);
    root = merge(merge(y, x), z);
}

void bottom(int s) {
    int p = get_rank(st[s], root);
    int x, y, z;
    split(root, p, x, z);
    split(x, p - 1, x, y);
    root = merge(merge(x, z), y);
}

void change(int s, int t) {
    if (!t) return;
    int p = get_rank(st[s], root);
    int x, y, z, l, r;
    if (t > 0) {
        split(root, p + 1, x, l);
        split(x, p, x, z);
        split(x, p - 1, x, y);
    }
    else {
        split(root, p, x, l);
        split(x, p - 1, x, z);
        split(x, p - 2, x, y);
    }
    root = merge(x, merge(z, merge(y, l)));
}

int ask(int p) {
    return get_rank(st[p], root);
}

int query(int p) {
    int x, y, z;
    split(root, p, x, z);
    split(x, p - 1, x, y);
    int ans = tr[y].key;
    root = merge(merge(x, y), z);
    return ans;
}

int n, m;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        insert(i, x);
    }

    char opt[10];
    int t1, t2;
    while (m--) {
        cin >> opt;
        if (opt[0] == 'T') {
            cin >> t1;
            top(t1);
        }
        else if (opt[0] == 'B') {
            cin >> t1;
            bottom(t1);
        }
        else if (opt[0] == 'I') {
            cin >> t1 >> t2;
            change(t1, t2);
        }
        else if (opt[0] == 'A') {
            cin >> t1;
            cout << ask(t1) - 1 << '\n';
        }
        else if (opt[0] == 'Q') {
            cin >> t1;
            cout << query(t1) << '\n';
        }
    }
    return 0;
}

标签：idx,int,root,tr,Treap,key,图解,FHQ,size
From： https://www.cnblogs.com/PlayWithCPP/p/17548297.html

相关文章

  • zookeeper作为注册中心，实现服务注册以及服务发现的思路图解
    一、服务发现 二、服务的发现： ......
  • 图解算法数据结构
    算法复杂度1.算法复杂度旨在输入数据量N的情况下，算法的时间和空间使用情况，体现算法运行使用的时间和空间随数据大小N而增大的速度。 算法复杂度主要可以从时间，空间两个角度评价：时间：假设各操作的运行时间为固定常数，统计算法运行的计算操作的数量，以代表算法运行所需时间......
  • 旋转Treap树
    #include<bits/stdc++.h>usingnamespacestd;constintM=1e6+10;intcnt=0;//cnt记录当前节点个数，最新一个节点即t[cnt]introot=0;//root是整棵树的树根，初始为空树所以root初始化=0intn;//n表示操作次数structNode{ intls,rs;//左右儿子 intval,pr......
  • 图解 MySQL 索引：B-树、B+树，终于搞清楚了
    看了很多关于索引的博客，讲的大同小异。但是始终没有让我明白关于索引的一些概念，如B-Tree索引，Hash索引，唯一索引….或许有很多人和我一样，没搞清楚概念就开始研究B-Tree，B+Tree等结构，导致在面试的时候答非所问！索引是什么?索引是帮助MySQL高效获取数据的数据结构。索引能干什......
  • 图解：什么是红黑树？
    本文转载自：https://zhuanlan.zhihu.com/p/273829162 注：本文比较硬核但是很值得大家花心思看完，看完你一定会有所收获的红黑树是面试中一个很经典也很有难度的知识点，网传字节跳动面试官最喜欢问这个问题。很多人会觉得这个知识点太难，不想花太多功夫去了解，也有人会认为这个数据结......
  • MySQL基础篇：逻辑架构图解和InnoDB存储引擎详解
    一、MySQL逻辑架构1、逻辑架构图基于下面的逻辑架构图，可以大致熟悉MySQL各个架构组件之间的协同工作关系。 很经典的C/S架构风格，即客户端/服务端模式。2、分层描述客户端连接通常会进行连接池管理，连接用户权限认证，安全管理等操作。可以通过如下命令查看连接配置信息：S......
  • N8、图解Transformer
    ......
  • Spring Boot视图解析
    视图解析：SpringBoot默认不支持JSP，需要引入第三方模板引擎技术实现页面渲染。thymeleaf使用：引入Starter<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-thymeleaf</artifactId><......
  • Swift开发图解入门
    《论语·卫灵公》有一段经典对白：『子贡问为仁。子曰：工欲善其事，必先利其器。……』。对于一个程序员来说，好的工具不意味着一定能产生优质的代码，但是好的工具对提升开发效率的作用还是不言而喻的。想要用Swift做iOS开发，唯一可选的利器就是Xcode6了，童鞋们可以从下面的网站获得Xcode6的......
  • 图解transformer中的自注意力机制
    本文将将介绍注意力的概念从何而来，它是如何工作的以及它的简单的实现。注意力机制在整个注意力过程中，模型会学习了三个权重:查询、键和值。查询、键和值的思想来源于信息检索系统。所以我们先理解数据库查询的思想。假设有一个数据库，里面有所有一些作家和他们的书籍信息。现在......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99