首页 > 其他分享 >【学习笔记】FHQ-Treap

【学习笔记】FHQ-Treap

时间:2023-10-23 17:12:10浏览次数:34  
标签:val merge int tree 笔记 Treap ls now FHQ

前置知识:二叉搜索树与二叉堆。

1. 简介

Treap,即 Tree+Heap,它的每个结点上存储着一个索引 \(key\) 和一个值 \(val\),其中索引满足二叉堆的性质,值满足二叉搜索树的性质,且索引是随机的。Treap 就是通过上述的性质,使树达到平衡。

至于为什么索引是随机的,其实很简单:我们插入的每个数的索引都要满足二叉堆的性质,而用随机数就会出现插入后不知道跑到哪里去了的情况,相当于做到了插入次序随机。

你问我二叉搜索树和二叉堆的性质是啥?自己补前置知识去。

而 Fhq-Treap (防火墙?),就是由范浩强大佬发明的无需旋转操作即可实现的 Treap,也称无旋 Treap,有着代码短、好理解、易于初学者学习等诸多优点。除了 LCT 必须写 Splay 以外(Fhq-Treap 会 TLE),其他平衡树能干的它基本上都能干。

2. 基本操作

Fhq-Treap 的核心操作其实只有两个:分裂与合并。

首先个人习惯写一个结构体来存储每个结点的信息:

struct node{
	int ls,rs;  //左右儿子结点的编号
	int val,key,siz;
}tree[maxn];

然后是一个新建结点的函数,并返回该结点的编号:

mt19937 rnd(233);
inline int newnode(int val){
	tree[++cnt_node].val=val;
	tree[cnt_node].key=rnd();
	tree[cnt_node].siz=1;
	return cnt_node;
}

基础的信息上传合并:

inline void pushup(int now){
	tree[now].siz=tree[ls(now)].siz+tree[rs(now)].siz+1;
}

同时为了写起来方便:

#define ls(k) tree[k].ls
#define rs(k) tree[k].rs

然后就可以往下看了。

分裂(split)

提前声明下,分裂操作分为两种:按值分裂和按大小分裂。一般如果把 fhq-Treap 当一棵普通的平衡树的话,都是使用前者的,本文所讲的也是按值分裂。

分裂操作会将整棵树分裂为两棵树 \(x\) 和 \(y\),且 \(x\) 中的值全部小于等于给定的值,\(y\) 中的值全部大于给定的值。

至于为什么这样分裂,你稍微看下模板题的操作应该就明白了。

至于代码,通过递归的方式来实现,详见注释:

void split(int now,int val,int &x,int &y){  //将树按val分裂成两棵树,分别以x和y为根
	if(!now){  //分到底了,返回
		x=y=0;
		return;
	}
	if(tree[now].val<=val){  //如果当前的值小于给定的,那么根据二叉搜索树的性质,给定的值一定在右子树中
		x=now;  //先确定其中一个根
		split(rs(now),val,rs(now),y);  //然后再去右子树分裂,这个自己稍微想一下,不难理解
	}
	else{  //反之亦然,给定值一定在左子树中
		y=now;
		split(ls(now),val,x,ls(now));
	}
	pushup(now);  //儿子都变了,更新信息
}

合并(merge)

合并操作会将两棵树 \(x\) 和 \(y\) 合并为一棵,前提条件为 \(x\) 内的所有值都小于等于 \(y\) 内的所有值,同时合并后的树仍然满足 Treap 的性质。

代码仍然还是通过递归的方式来实现,如下所示:

int merge(int x,int y){  //将x和y合并为一棵树,并将合并后的根返回
	if(!x||!y) return x^y;  //这个其实就是x+y,也就是x和y中不为0的那一个,这种情况表示其中有棵树为空
	if(tree[x].key>tree[y].key){  //忘记题的一点,这里默认大根堆
		rs(x)=merge(rs(x),y);  //注意还要满足二叉搜索树的性质
		pushup(x);  //更新信息
		return x;
	}
	else{  //反之亦然
		ls(y)=merge(x,ls(y));  //为满足二叉搜索树
		pushup(y);  //更新信息
		return y;
	}
}

到此为止,Fhq-Treap 最核心的部分你已经学完了。

3. 其它操作

先送上模板题

有了以上两个核心操作后,我们应该怎么实现其他平衡树的操作呢?相信各位读者看懂了上面后口胡出来都没问题。

接下来让我们挨个分析。

插入

假如我们要插入的值为 \(val\),那么我们可以按照 \(val\) 将原树分裂为 \(x\) 和 \(y\),然后根据上文的定义,\(x\) 中的所有值一定都小于等于 \(val\),因此可以直接将 \(x\) 和新结点合并,然后再重新与 \(y\) 合并即可。

代码只需两行即可搞定:

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

删除

假如我们要删除的值为 \(val\),那么我们可以按照 \(val\) 将原树分裂为 \(x\) 和 \(y\),然后再按照 \(val-1\) 将 \(x\) 再分裂为 \(x\) 和 \(z\),同样根据上文的定义,此时 \(z\) 中的值一定全都与 \(val\) 相等。这个时候,我们可以去掉 \(z\) 的根节点,最后再都重新合并回去即可。

代码比插入长个两行:

inline void erase(int val){
	split(root,val,x,y);  
	split(x,val-1,x,z);
	z=merge(ls(z),rs(z));
	root=merge(merge(x,z),y);
}

查询给定值的排名

设要查询的值为 \(val\),那么我们可以按照 \(val-1\) 将原树分裂为 \(x\) 和 \(y\),然后此时左子树的大小就是比 \(val\) 小的值的个数,再加上 \(1\) 就是答案。

别忘了合并回去哈。

inline int get_rank(int val){
	split(root,val-1,x,y);
	int ret=tree[x].siz+1;
	root=merge(x,y);
	return ret;
}

查询给定排名的值

这个也很简单,根据二叉搜索树的性质即可:若当前的左子树大小大于给定排名,答案就在左子树中,否则就去右子树。

注意去右子树的话,要将查询的排名减去左子树的大小,再包括自己占的一个。

写法上递归与非递归皆可。

递归写法:

int get_val(int now,int k){
	if(tree[ls(now)].siz+1==k) return tree[now].val;
    else if(tree[ls(now).siz]>=k) return get_val(ls(now),k);
    else return get_val(rs(now),k-tree[ls(now)].siz-1);
}

非递归写法:

int get_val(int rnk){
	int now=root;
	while(now){
		if(tree[ls(now)].siz+1==rnk) break;
		else if(tree[ls(now)].siz>=rnk) now=ls(now);
		else rnk-=tree[ls(now)].siz+1,now=rs(now);
	}
	return tree[now].val;
}

查询前驱

设要查询的值为 \(val\),那么我们可以将原树按 \(val-1\) 分裂为 \(x\) 和 \(y\),然后根据二叉搜索树的性质,我们在 \(x\) 中一直往右跳就可以找到前驱了。

int get_pre(int val){
	split(root,val-1,x,y);
	int now=x,ret;
	while(rs(now)) now=rs(now);
	ret=tree[now].val;root=merge(x,y);
	return ret;
}

查询后继

设要查询的值为 \(val\),那么我们可以将原树按照 \(val\) 分裂为 \(x\) 和 \(y\),然后根据二叉搜索树的性质,我们在 \(y\) 中一直往左跳就可以找到后继了。

int get_nxt(int val){
	split(root,val,x,y);
	int now=y,ret;
	while(ls(now)) now=ls(now);
	ret=tree[now].val;root=merge(x,y);
	return ret;
}

好的,至此平衡树模板的所有操作我们都已经用分裂和合并这两个基础操作实现出来了!

4. 代码

行数114(警觉)

#include<bits/stdc++.h>
#define int long long
#define ls(k) tree[k].ls
#define rs(k) tree[k].rs
using namespace std;
const int maxn=1e5+5;
const int inf=0x7fffffff;
int read(){
	int ans=0,flag=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')flag=-1;ch=getchar();}
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
	return ans*flag;
}
struct node{
	int ls,rs;
	int val,key,siz;
}tree[maxn];
int cnt_node,root,x,y,z;
mt19937 rnd(233);
int newnode(int val){
	tree[++cnt_node].val=val;
	tree[cnt_node].key=rnd();
	tree[cnt_node].siz=1;
	return cnt_node;
}
void pushup(int now){
	tree[now].siz=tree[ls(now)].siz+tree[rs(now)].siz+1;
}
void split(int now,int val,int &x,int &y){
	if(!now){
		x=y=0;
		return;
	}
	if(tree[now].val<=val){
		x=now;
		split(rs(now),val,rs(now),y);
	}
	else{
		y=now;
		split(ls(now),val,x,ls(now));
	}
	pushup(now);
}
int merge(int x,int y){
	if(!x||!y) return x^y;
	if(tree[x].key>tree[y].key){
		rs(x)=merge(rs(x),y);
		pushup(x);
		return x;
	}
	else{
		ls(y)=merge(x,ls(y));
		pushup(y);
		return y;
	}
}
inline void insert(int val){
	split(root,val,x,y);
	root=merge(merge(x,newnode(val)),y);
}
inline void erase(int val){
	split(root,val,x,y);
	split(x,val-1,x,z);
	z=merge(ls(z),rs(z));
	root=merge(merge(x,z),y);
}
inline int get_rank(int val){
	split(root,val-1,x,y);
	int ret=tree[x].siz+1;
	root=merge(x,y);
	return ret;
}
int get_val(int rnk){
	int now=root;
	while(now){
		if(tree[ls(now)].siz+1==rnk) break;
		else if(tree[ls(now)].siz>=rnk) now=ls(now);
		else rnk-=tree[ls(now)].siz+1,now=rs(now);
	}
	return tree[now].val;
}
int get_pre(int val){
	split(root,val-1,x,y);
	int now=x,ret;
	while(rs(now)) now=rs(now);
	ret=tree[now].val;root=merge(x,y);
	return ret;
}
int get_nxt(int val){
	split(root,val,x,y);
	int now=y,ret;
	while(ls(now)) now=ls(now);
	ret=tree[now].val;root=merge(x,y);
	return ret;
}
signed main(){
	int Q=read();
	while(Q--){
		int opt=read(),x=read();
		if(opt==1) insert(x);
		else if(opt==2) erase(x);
		else if(opt==3) printf("%lld\n",get_rank(x));
		else if(opt==4) printf("%lld\n",get_val(x));
		else if(opt==5) printf("%lld\n",get_pre(x));
		else if(opt==6) printf("%lld\n",get_nxt(x));
	}
	return 0;
}

标签:val,merge,int,tree,笔记,Treap,ls,now,FHQ
From: https://www.cnblogs.com/los114514/p/17782938.html

相关文章

  • 随手笔记:Swagger 报错 NO Found /swagger/V1/swagger.json
    开发本地测试没问题,发布iis报错原因:swagger判断开发环境和发布环境解决办法:在startup.cs文件中找到调用swagger方法不做判断app.UseSwagger();      app.UseSwaggerUI(c=>c.SwaggerEndpoint("/swagger/v1/swagger.json","MyWebAPIV1"));如图所示:......
  • 学习笔记6
    苏格拉底挑战第三章Unix/Linux进程管理一.知识点归纳(一)多任务处理多任务处理是所有操作系统的基础。总体上说,它也是并行编程的基础。(二)进程的概念进程是对映像的执行。在操作系统内核中,每个进程用一个独特的数据结构表示,叫作进程控制块(PCB)或任务控制块(TCB)等。......
  • Hive学习笔记:多列求最大值、最小值
    一、最大值当在Hive中需要对多列数据求最大值时,可以使用函数greatest(a,b,c,d)实现。selectgreatest(a,b,c)from( select10asa,20asb,30asc)dd;--结果:30举个具体栗子:计算用户消费时,如果用户套餐有最低消费129元的话,不满12......
  • CSAPP 第一章 笔记
    硬件组成总线I/O设备键盘,鼠标,显示器,磁盘...主存处理器(CPU)寄存器hello程序的生命周期源文件hello.c文本文件:位序列字节:8个位为一组ASCII码可执行目标文件Unix:通过编译器驱动程序完成编译系统预处理器‘#’,hello.i编译器‘main’,hello.s汇编器翻译成......
  • 笔记:Qt开发之多线程同步互斥机制
    目标:了解Qt多线程开发中常用的同步互斥类,使用场景和特点 实现线程互斥和同步常用的类互斥锁:QMute、QMutexLocker条件变量:QWaitCondition信号量:QSemaphore读写锁:QReadLocker、QWriteLocker、QReadWriteLock 1,QMutex特点:QMutex是Qt框架提供的互斥锁类,用于保护共享资......
  • 第三周阅读笔记|人月神话————为什么巴比伦塔会失败
    巴比伦塔的管理教训巴比伦塔是人类继诺亚方舟之后的第二大工程壮举,但巴比伦塔同时也是第一个彻底失败的工程。现在,其实也是这样的情况。因为左手不知道右手在做什么,所以进度灾难、功能的不合理和系统缺陷纷纷出现。随着工作的进行,许多小组慢慢地修改自己程序的功能、规模和速度,他......
  • ServerLess学习笔记-Fnproject搭建
    ServerLess学习笔记-搭建FnProject介绍官方文档:https://fnproject.io/tutorials/Fn是一个事件驱动的开源功能即服务FaaS计算平台,您可以在任何地方运行,它的一些主要特点开源原生Docker:使用任何Docker容器作为你的函数支持所有语言随处运行公有云、私有云和混合云......
  • ServerLess学习笔记-搭建FN示例
    ServerLess学习笔记-搭建FnProject示例初始化函数目录#初始化fn_demo1[root@VM-24-9-centosserverless]#fninit--runtimepythonfn_demo1Creatingfunctionat:./fn_demo1UnabletogetlatestFDKversion,usingdefaultFunctionboilerplategenerated.func.yam......
  • ServerLess学习笔记-Fnproject常用命令
    ServerLess学习笔记-FnProject常用命令启动/停止#启动fnstart#停止fnstop创建[root@VM-24-9-centosserverless]#fncreateMANAGEMENTCOMMANDfncreate-CreateanewobjectUSAGEfn[globaloptions]create[command......
  • Programming abstractions in C阅读笔记:p181-p183
    《ProgrammingAbstractionsInC》学习第61天,p181-p183总结。一、技术总结1.linearsearchalgorithm2.lexicographicorder(字典顺序)3.binarysearchalgorithm(二分查找算法)/**1.二分查找也应用了递归的思想。*2.这里的代码只是demo*/#include<stdio.h>#incl......