专栏首页数据结构与算法FHQ Treap小结(神级数据结构!)

FHQ Treap小结(神级数据结构!)

首先说一下,

这个东西可以搞一切bst,treap,splay所能搞的东西

pre

今天心血来潮,

想搞一搞平衡树,

先百度了一下平衡树,发现正宗的平衡树写法应该是在二叉查找树的基础上加什么左左左右右左右右的旋转之类的,

思路比较好理解,但是

代码量。。。。。。。。

一看就头大,,

然后,在洛谷翻题解的时候无意间看到了远航之曲发的一篇非常短小精悍的题解,

于是就学了一下

FHQ Treap

这个东西的学名应该是叫做fhq treap,应该是treap的强化版。

整个数据结构中只有两个操作:

1.分离(split) 就是把一棵树分成两个树

2.合并(merge)把两棵树合成一棵树

对于FHQ 的两种操作的原理以及实现,

我在这里就不去赘述,

大家可以去看一下远航之曲写的博客

http://www.yhzq-blog.cc/fhq-treap%e6%80%bb%e7%bb%93/

在这里我主要是在讲解一下代码的具体实现(当然也有可能不对。。)

CODE

题目链接:

https://www.luogu.org/problem/show?pid=3369

先说一下各个数组的含义:

1 int ch[MAXN][3];// 0左孩子 1右孩子
2 int val[MAXN];// 每一个点的权值
3 int pri[MAXN];// 随机生成的附件权值
4 int siz[MAXN];// 以i为节点的树的节点数量
5 int sz;// 总结点的数量 

然后来分别说明一下六中操作的实现

1.插入:

split(root,a,x,y);
root=merge(merge(x,new_node(a)),y);

这个比较好理解,我们先把树分为x,y两部分,然后把新的节点a看做是一棵树,先与x合并,合并完之后将合并的整体与y合并

2.删除

1 split(root,a,x,z);
2 split(x,a-1,x,y);
3 y=merge(ch[y][0],ch[y][1]);
4 root=merge(merge(x,y),z);

首先我们把树分为x和z两部分

那么x树中的最大权值为a

再把x分为x和y两部分。

此时x中的最大权值为a-1,且权值为a的节点一定是y的根节点。

然后我们可以无视y的根节点,直接把y的左右孩子合并起来,这样就成功的删除了根节点,

最后再把x,y,z合并起来就好

3.查询a的排名

1 split(root,a-1,x,y);
2 printf("%d\n",siz[x]+1);
3 root=merge(x,y);

我们首先按照a-1的权值把树分开。

那么x树中最大的应该是a-1。

那么a的排名就是siz[x]+1

4.查询排名为a的数

1 printf("%d\n",val[kth(root,a)]);

直接调用查找排名的函数即可,

这个函数应该比较好理解。。

5.求x的前驱(前驱定义为小于a,且最大的数)

1 split(root,a-1,x,y);
2 printf("%d\n",val[kth(x,siz[x])]);
3 root=merge(x,y);

因为要小于a,那么我们按照a-1的权值划分,

x中最大的一定是<=a-1的,

所以我们直接输出x中最大的数就好,

(这里有一个小技巧,因为siz储存的是节点的数目,然后根据二叉查找树的性质,编号最大的就是值最大的)

6.求x的后继(后继定义为大于x,且最小的数)

1 split(root,a,x,y);
2 printf("%d\n",val[kth(y,1)]);
3 root=merge(x,y);

和上面的原理类似,

留给大家思考,

不懂的再问我。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<ctime>
  8 using namespace std;
  9 const int MAXN=100001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 int ch[MAXN][3];// 0左孩子 1右孩子
 18 int val[MAXN];// 每一个点的权值
 19 int pri[MAXN];// 随机生成的附件权值
 20 int siz[MAXN];// 以i为节点的树的节点数量
 21 int sz;// 总结点的数量 
 22 void update(int x)
 23 {
 24     siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
 25 } 
 26 int new_node(int v)
 27 {
 28     siz[++sz]=1;// 新开辟一个节点
 29     val[sz]=v;
 30     pri[sz]=rand(); 
 31     return sz;
 32 }
 33 int merge(int x,int y)// 合并 
 34 {
 35     if(!x||!y)    return x+y;// x和y中必定有一个是0
 36     if(pri[x]<pri[y])// 把x加到左边的树上 
 37     {
 38         ch[x][1]=merge(ch[x][1],y);// 不懂的看GIF图 
 39         update(x);
 40         return x;
 41     } 
 42     else
 43     {
 44         ch[y][0]=merge(x,ch[y][0]);
 45         update(y);
 46         return y;
 47     }
 48 }
 49 void split(int now,int k,int &x,int &y)
 50 {
 51     if(!now) x=y=0;// 到达叶子节点
 52     else
 53     {
 54         if(val[now]<=k)// 分离右子树    
 55             x=now,split(ch[now][1],k,ch[now][1],y);
 56         else 
 57             y=now,split(ch[now][0],k,x,ch[now][0]);
 58         update(now);
 59     } 
 60 }
 61 int kth(int now,int k)// 查询排名 
 62 {
 63     while(1)
 64     {
 65         if(k<=siz[ch[now][0]])
 66             now=ch[now][0];// 在左子树中,且数量小于左子树的大小,迭代寻找
 67         else if(k==siz[ch[now][0]]+1)
 68             return now;// 找到了
 69         else 
 70             k-=siz[ch[now][0]]+1,now=ch[now][1];// 去右子树找 
 71     }
 72 }
 73 int main()
 74 {
 75     srand((unsigned)time(NULL));
 76     int n;
 77     read(n);
 78     int root=0,x,y,z;
 79     for(int i=1;i<=n;i++)
 80     {
 81         int how,a;
 82         read(how);read(a);
 83         if(how==1)// 插入 
 84         {
 85             split(root,a,x,y);
 86             root=merge(merge(x,new_node(a)),y);
 87         }
 88         else if(how==2)//删除x 
 89         {
 90             split(root,a,x,z);
 91             split(x,a-1,x,y);
 92             y=merge(ch[y][0],ch[y][1]);
 93             root=merge(merge(x,y),z);
 94         }
 95         else if(how==3)//查询x的排名 
 96         {
 97             split(root,a-1,x,y);
 98             printf("%d\n",siz[x]+1);
 99             root=merge(x,y);
100         }
101         else if(how==4)// 查询排名为x的数 
102         {
103             printf("%d\n",val[kth(root,a)]);
104         }
105         else if(how==5)// 求x的前驱 
106         {
107             split(root,a-1,x,y);
108             printf("%d\n",val[kth(x,siz[x])]);
109             root=merge(x,y);
110         }
111         else if(how==6)// 求x的后继 
112         {
113             split(root,a,x,y);
114             printf("%d\n",val[kth(y,1)]);
115             root=merge(x,y);
116         }
117     }
118     return 0;
119 }

最后说一下,FHQ其实是可以处理区间问题的,

主要就是先把r+1的拆出来,然后把l的拆出来。

但是有些细节问题特别神奇,至今没有搞懂。

如果你会的话希望你能给本蒟蒻讲一下。

谢谢

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P3369 【模板】普通平衡树(Treap/SBT)

    题目描述 您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作: 插入x数 删除x数(若有多个相同的数,因只删除一个) 查询...

    attack
  • P3391 文艺平衡树

    hh 题目描述 您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[...

    attack
  • 洛谷P3966 [TJOI2013]单词(AC自动机)

    attack
  • 回文素数

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 2014 360校园招聘技术类笔试题

    原文:http://blog.csdn.net/lanxuezaipiao/article/details/41892553

    bear_fish
  • POJ2155

    因为最近准备模板,所以把不太常用的算法又熟悉了一边,发现果然不练不行。 二维线段树,树套树 #include<iostream> #include<cstdio...

    triplebee
  • 为什么说Python是伟大的入门语言

    本文作者列举了一些Python特性,并认为Python是最适合入门的编程语言,一起来看一下。 最近发表了三篇关于我的艺术史背景是如何影响我教学的文章。现在要分享...

    CSDN技术头条
  • Student Attendance Record I

    Tyan
  • 数据库中间件cobar调研笔记

    13年底负责数据库中间件设计时的调研笔记,拿出来和大家分享,轻拍。文章很长,可提前收藏,转发。 一,cobar是什么 开源的mysql的中间件服务 使用mysq...

    架构师之路
  • Java快速入门教程 3、使用IntelliJ IDEA+Maven 创建、开发、管理项目

    在 POM 中,groupId, artifactId, packaging, version 叫作 maven 坐标,它能唯一的确定一个项目。有了 maven...

    KenTalk

扫码关注云+社区

领取腾讯云代金券