首页 > 其他分享 >弱势无图解FHQ-Treap 及各种乱七八糟的错误方法

弱势无图解FHQ-Treap 及各种乱七八糟的错误方法

时间：2023-08-22 11:44:46浏览次数：41  
标签：Merge vlx int pos 错误方法 son Treap FHQ

众所周知，FHQ-Treap是一个码量少，可区间翻转，能持久化的treap（只是常熟略大）
像我这种蒟蒻，想调处有旋Treap或者Splay肯定要个114514年

以下可能以FHQ代表FHQ-Treap（逃

前置芝士

treap的节点拥有两个权值，一个是值，一个是优先级。优先级满足堆的性质，值满足二叉搜索树的性质。
当两个权值相同时，treap是固定的。堆的性质以及随机的优先级可以让树深保持在\(\log n\)，确保时间复杂度；而二叉搜索树可以带来求排名，前驱，后继等操作。

前置提醒

FHQ-Treap 的合并要求一个FHQ的值全部小于等于另一个，建议是确定一下哪个大，哪个小。这里以左小右大为例.

操作

1、Update

这个就是和线段树一模一样的Update，不保熟（

void Update(int pos)
{
	siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;
}

siz即FHQ的大小，son[pos][0]代表左儿子,son[pos][1]代表右儿子

2、Split

字面意思，将一个FHQ按权值\(val\)分成小于等于和大于两个。
我们将一个FHQ分成\(x\)、\(y\)两个（即根节点为\(x\)、\(y\)）本文中左（即\(x\)FHQ）一律小于右（即\(y\)FHQ）

假设我们在原FHQ的节点\(pos\)

若该点的值大于\(val\)由二叉搜索树可知该点和它的右子树节点都大于\(val\),将其置入右(y)FHQ
并在左子树中寻找也大于\(val\)的子树，归入该点在\(y\)FHQ所在点的左子树中

若该点的值小于等于\(val\)由二叉搜索树可知该点和它的左子树节点都小于等于\(val\),将其置入左(x)FHQ
并在右子树中寻找也小于等于\(val\)的子树，归入该点在\(x\)FHQ所在点的右子树中
（可能有点绕）
回溯时记得及时在该点Update以保证子树大小正确。

若\(pos\)为0，即空子树，便无法再分

void Split(int pos,int vlx,int &x,int &y)
{
	if(pos==0)
	{
		x=y=0;
		return;
	}
	if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);
	else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);
	Update(pos);
}

3、Merge

将两个FHQ合并，要求一个FHQ的所有值都小于等于另一个。
由于值都是已经有大小的，我们可以将\(x\)置入\(y\)的左子树或将\(y\)置入\(x\)的右子树
但我们要使优先级满足堆的性质

再次假设我们在两个FHQ的节点\(x\)和\(y\) 这里以小根堆为例

若\(x\)的优先级大于\(y\)优先级，由堆可知\(x\)和它的子树节点的优先级都大于\(y\)的优先级,因为\(x\)的值小于等于\(y\),将其加在\(y\)的左子树下

若\(x\)的优先级小于\(y\)优先级，由堆可知\(y\)和它的子树节点的优先级都大于\(x\)的优先级,因为\(y\)的值大于\(y\),将其加在\(x\)的右子树下

这里等于的条件归在哪都无所谓

回溯时记得及时在该点Update以保证子树大小正确。

若\(x\),\(y\)有一个或多个为0，即存在空节点，直接返回另一个节点或0即可

int Merge(int x,int y)
{
	if(x==0||y==0)
	return x+y;
	if(rnd[x]>rnd[y])
	{
		son[y][0]=Merge(x,son[y][0]),Update(y); return y;
	}
	else
	{
		son[x][1]=Merge(son[x][1],y),Update(x); return x;
	}
}

4、Get

获得排名为\(vlx\)的树
本文将相同的点归在同一点，使用cnt记录
其实也可当作不同的点只需修改下Get和插入
这里其实和不同的BST一样
若\(vlx\)小于等于左子树大小，则进入左子树
若\(vlx\)大于左子树大小+该节点个数（即总个数-右子树大小），则减去左子树大小和该点的cnt，进入右子树
若\(vlx\)大于左子树大小且小于等于左子树大小+该节点个数，该排名就是该节点的值，return即可

int Get(int pos,int vlx)
{
	if(vlx<siz[son[pos][0]]+1) return Get(son[pos][0],vlx);
	if(vlx>siz[son[pos][0]]+cnt[pos])
	return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);
	return val[pos];
}

以上的方法都是\(O(log n)\)的，每次都是进入左子树或右子树，总共不超过\(log n\)层

接下来是不用递归的功能

1、插入

要插入\(vlx\)值
现将原FHQ分裂出小于等于\(vlx\)的\(x\)和大于的\(y\)
再从\(x\)中分出小于等于\(vlx\)的\(x'\)和等于\(vlx\)的\(z\)
若\(z\)存在，给节点\(z\)的副本数和大小都加1
不存在，则新建一个\(z\)节点
再按顺序Merge回去

	Split(Root,vlx,x,y);
	Split(x,vlx-1,x,z);
	if(z==0) New(z,vlx);
	else cnt[z]++,siz[z]++;
	Root=Merge(Merge(x,z),y);

2、删除

说道删除，FHQ直接呵呵嗨
只需按插入的方法分出\(x\)
若\(z\)存在且副本数大于一，给节点\(z\)的副本数和大小都减1
若副本数等于一，直接丢到垃圾桶里（
若\(z\)不存在，？？？删不存在的数？？？

	Split(Root,vlx,x,y);
	Split(x,vlx-1,x,z);
	if(cnt[z]>1) cnt[z]--,siz[z]--;
	else z=0;
	Root=Merge(Merge(x,z),y);

3、查排名

按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ
答案即是\(x\)大小加1

	Split(Root,vlx-1,x,y);
	write(siz[x]+1),pc('\n');
	Root=Merge(x,y);

4、查排名对应的树

调用Get即可

	write(Get(Root,vlx)),pc('\n');

5、前驱

按\(vlx-1\)分裂出小于等于\(vlx-1\)的\(x\)FHQ
\(x\)中的最大值及是x中排名做后的
Get出\(x\)中排名为\(siz[x]\)的即可

	Split(Root,vlx-1,x,y);
	write(Get(x,siz[x])),pc('\n');
	Root=Merge(x,y);

6、后继

按\(vlx\)分裂出大于\(vlx\)的\(y\)FHQ
\(y\)中的最小值及是y中排名第一的
Get出\(x\)中排名为1的即可

	Split(Root,vlx,x,y);
	write(Get(y,1)),pc('\n');
	Root=Merge(x,y);

附上完整代码

点击查看代码 
#include<bits/stdc++.h>
#define fo(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define Ts template<typename Ty,typename... Ar>
#define Tp template<typename Ty>
#define ll long long
#define RS register
#define gc getchar
#define pc putchar
#define I inline
using namespace std;
Tp I Ty wmax(Ty a,Ty b){return a>=b? a:b;}
Tp I Ty wmin(Ty a,Ty b){return a<=b? a:b;}
namespace WrongIO
{
	Tp I void read(Ty &x){x=0;Ty opt=1;char c=gc();while(!isdigit(c)&&c!='-')c=gc();if(c=='-')opt=-1,c=gc();while(isdigit(c))x=(x<<3)+(x<<1),x+=c-'0',c=gc();x*=opt;return;}
	Tp I void write(Ty x){short OI_USE[50],OI_top=0;if(x<=0) if(x==0)pc('0');else pc('-'),x*=-1;while(x)OI_USE[++OI_top]=x%10,x/=10;while(OI_top--)pc(OI_USE[OI_top+1]+'0');return;}
    I void writec(char c[]){int len=strlen(c);for(int i=0;i<len;i++)pc(c[i]);}
    I void writes(string s){int len=s.length();for(int i=0;i<len;i++)pc(s[i]);}
    I void readc(char &c,int l,int r){c=gc(); while(c!=EOF&&(c<l||c>r)) c=gc();}
    I void readc(char &c,char val){c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readc(char val){char c;c=gc();while(c!=EOF&&c!=val) c=gc();}
    I void readls(string &s){char c=gc();while(c!='\n') s.push_back(c),c=gc();}
    Ts I void read(Ty &x,Ar &...y) {read(x),read(y...);}
} using namespace WrongIO;
int val[100050],cnt[100050],rnd[100050],siz[100050],son[100050][2],ct;
int n,Root;
void Update(int pos)
{
	siz[pos]=cnt[pos]+siz[son[pos][0]]+siz[son[pos][1]]; return;
}
void New(int &id,int vlx)
{
	id=++ct;
	val[id]=vlx;
	rnd[id]=rand();
	siz[id]=cnt[id]=1;
	return;
}
int Merge(int x,int y)
{
	if(x==0||y==0)
	return x+y;
	if(rnd[x]>rnd[y])
	{
		son[y][0]=Merge(x,son[y][0]),Update(y); return y;
	}
	else
	{
		son[x][1]=Merge(son[x][1],y),Update(x); return x;
	}
}
void Split(int pos,int vlx,int &x,int &y)
{
	if(pos==0)
	{
		x=y=0;
		return;
	}
	if(val[pos]<=vlx) x=pos,Split(son[pos][1],vlx,son[pos][1],y);
	else y=pos,Split(son[pos][0],vlx,x,son[pos][0]);
	Update(pos);
}
int Get(int pos,int vlx)
{
	if(vlx<siz[son[pos][0]]+1) return Get(son[pos][0],vlx);
	if(vlx>siz[son[pos][0]]+cnt[pos])
	return Get(son[pos][1],vlx-siz[son[pos][0]]-cnt[pos]);
	return val[pos];
}
int main(){
	//fo("input5");
	read(n);
	for(int i=1;i<=n;i++)
	{
		int opt,vlx,x,y,z; read(opt,vlx);
		if(opt==1)
		{
			Split(Root,vlx,x,y);
			Split(x,vlx-1,x,z);
			if(z==0) New(z,vlx);
			else cnt[z]++,siz[z]++;
			Root=Merge(Merge(x,z),y);
		}
		if(opt==2)
		{
			Split(Root,vlx,x,y);
			Split(x,vlx-1,x,z);
			if(cnt[z]>1) cnt[z]--,siz[z]--;
			else z=0;
			Root=Merge(Merge(x,z),y);
		}
		if(opt==3)
		{
			Split(Root,vlx-1,x,y);
			write(siz[x]+1),pc('\n');
			Root=Merge(x,y);
		}
		if(opt==4)
		{
			write(Get(Root,vlx)),pc('\n');
		}
		if(opt==5)
		{
			Split(Root,vlx-1,x,y);
			write(Get(x,siz[x])),pc('\n');
			Root=Merge(x,y);
		}
		if(opt==6)
		{
			Split(Root,vlx,x,y);
			write(Get(y,1)),pc('\n');
			Root=Merge(x,y);
		}
	}
    return 0;
}//555,卡芙卡的池子歪了一个最不想要的姬子

雄氏老方，专治各种疑难杂症

1、FHQ-Treap真的短，好多都压成了一行写，导致Merge函数，忘写返回值了（
2、若将相同点合成一个点，在副本数加1的同时一定要给大小也加1，这个更新不到，减1同理
3、一定要明确两个FHQ的大小关系，不然会有奇怪的事发生
4、分裂中的两个分支容易写错，可能会出现死循环或导致死循环，发生MLE或TLE
5、一些地方要以值-1来分裂，要注意
6、Merge和Split在pos为0时记得退出
7-113、留给评论区
114、宇宙射线照射导致的UKE，雄氏老方也治不了（

标签：Merge,vlx,int,pos,错误方法,son,Treap,FHQ
From： https://www.cnblogs.com/JuyeScene/p/17648099.html

相关文章

  • Treap
    BST\(v_i\)表示点权，\(x\)表示当前点，\(L\)表示左子树，\(R\)表示右子树在普通二叉树的基础上多一个条件对于\(p\inL\)，满足\(v_p\leqv_x\)对于\(q\inR\)，满足\(v_x<v_q\)Treap但是这样如果BST是一条链的话就退化\(O(n)\)，而且很容易卡，考虑TreapTreap就是在普通B......
  • FHQ-Treap 详解
    目录1）FHQ-Treap基本功能理论与实现1.1）FHQ-Treap模型1.2）操作一：分裂（Split）1.3）操作二：合并（Merge）1.4）操作三：插入新节点1.5）删除某个节点1.6）查询某个值的排名1.7）查询排名为\(k\)的值1.8）查询\(x\)的前驱与后继1.9）Endofthisunit2）FHQ-Treap的应用2.1）洛谷P3369END1）FHQ-Treap基本功......
  • 『学习笔记』fhq-treap
    啥是平衡树这边建议去这里。分裂一般指的是按值分裂，意思就是以树上的BST（二叉搜索树）的值为关键值分裂。一般会给一个关键值\(val\)，把一棵平衡树分裂成BST值\(\leqval\)和\(>val\)的两部分。主要思想从根开始递归，递归到某一节点，如果当前根节点的BST值小于等于你给的那......
  • 无旋平衡树（范浩强Treap）平均时间复杂度证明
    范浩强Treap是一种应用广泛的数据结构（可参考OI_Wiki），然而网上难以找到比较严谨的复杂度证明.本文将严格证明\(n\)个结点的Treap的期望树高为\(\Theta(\logn)\)，由于一次分裂或合并操作的递归深度恰为树高，这便说明了一次操作的平均时间复杂度为\(\Theta(\logn)\).首先，由......
  • FHQ-Treap
    本文仅发布于此博客和作者的洛谷博客，不允许任何人以任何形式转载，无论是否标明出处及作者。前置废话fhq为什么是神。首先我们有一个正常Treap。正常Treap对于每一个值引入了一个随机的键，在节点的值形成一个BST的基础上，保证键形成一个小根堆。也就是把这一个BST做成了笛卡尔树......
  • 「学习笔记」FHQ-treap
    FHQ-treap，即无旋treap，又称分裂合并treap，支持维护序列，可持久化等特性。FHQ-treap有两个核心操作，分裂与合并。通过这两个操作，在很多情况下可以比旋转treap等方便的实现一些操作。FHQ-treap与其他的平衡树相比，他最明显的优点是：它好写！！！，想象一下，在考场上，你用较短的时间写出FH......
  • FHQ-Treap
    简介FHQ-Treap是一种无旋转的Treap。和大多数的平衡树不一样，它并不是用旋转来维护的，而是使用了split（分裂）和merge（合并）两种操作来维护Treap的性质。实现splitsplit操作可以将一个FHQ-Treap按照某个值分裂为两个FHQ-Treap：按照权值分：将权值\(\leval\)的放到一个......
  • FHQ-Treap的详细图解
    第一部分按值分裂的FHQ-Treap按值分裂的FHQ-Treap的典型例题是P3369【模板】普通平衡树。思路FHQ-Treap是什么？FHQ-Treap是二叉搜索树的一种。比如：FHQ-Treap的思想是什么？分裂->操作->合并下面我们就来慢慢讲这些操作。分裂我们可以根据给定的\(k\)将平衡树分......
  • 旋转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......
  • 旋转Treap
    splay是通过splay操作均摊复杂度，而旋转treap也旋转，但是是通过随机赋权使得复杂度在期望下正确。具体来说就是再随机赋一个权值\(rank\)，通过旋转使得这棵树的\(val\)满足二叉搜索树且\(rank\)满足小根堆。具体来说，在查询的时候是不旋转的，只有在插入和删除时有旋转。......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99