FHQ-Treap-526互联

本文仅发布于此博客和作者的洛谷博客，不允许任何人以任何形式转载，无论是否标明出处及作者。

前置废话

fhq为什么是神。

首先我们有一个正常Treap。

正常Treap对于每一个值引入了一个随机的键，在节点的值形成一个BST的基础上，保证键形成一个小根堆。也就是把这一个BST做成了笛卡尔树。

因为这个键是随机给的，所以树退化成链的形状的概率极其小，使得树深度期望是\(\log n\)级别的，从而避免了被毒瘤数据卡掉。

因为正常通过旋转维护小根堆的Treap码量较大，所以有了无旋Treap，即FHQ-Treap。FHQ-Treap好想好写，但是缺点也很明显，就是常数很大。我的实现甚至比Splay还要慢一倍。

Split操作

Split和下面的Merge为FHQ-Treap的两个最基本操作，其他操作都是在其基础上实现的。

Split的作用是给定一个数值\(x\)，把一整棵树拆成分开的两棵树，一棵所有节点的值\(\leq x\)，一棵节点的值\(>x\)。

Split是递归进行的：

设当前节点编号为\(k\)。如果其值\(\leq x\)，则把\(k\)放在\(\leq x\)的树中。因为\(k\)的左子树中所有节点的值都\(<k\)，所以\(k\)的整个左子树也应该放在\(\leq x\)的树中。

把其右子树拆开。右子树被拆成\(\leq x\)，\(>x\)的两棵树。把\(k\)的右子树更新成拆出来的\(\leq x\)的那棵树，我们就把以\(k\)为根的树拆成了两棵：以\(k\)为根，\(\leq x\)的一棵，和从右子树拆出来的\(>x\)那棵。

如果\(k\)的值\(>x\)，相似地，拆开左子树。把\(k\)的左子树更新成拆出来的\(>x\)的那棵树，同样把以\(k\)为根的树拆成了两棵：从左子树拆出来的\(\leq x\)，以\(k\)为根的\(>x\)。

纯文字不太好理解，我们举个例子，拆掉下面这棵树。

为了方便，每个节点的编号就是其权值。我们要把这棵树拆成\(\leq5\)，\(>5\)两棵分开的树。（节点\(9\)应该是\(10\)的左儿子。无所谓，不影响理解算法。）

红色树为\(\leq 5\)的树，蓝色为\(>5\)的树。

注意到，第4步以后到了不存在的空节点。此时直接返回并记两棵树的树根都为\(0\)。

最后，这棵树就被分成了这个样子。

这个例子里并没有展示节点的键，但是因为Split没有颠倒点之间的父子关系（即一个点的祖先Split后不会到其子树里），所以不需要考虑键。

思路写成代码如下。

struct FHQ_Treap{
	int key;//随机键
	int val;//真实值
	int lc;
	int rc;
	int size;//子树大小
}t[100005];
struct S{//S for Split，当然直接用pair<int,int>也可以
	int Lroot;//split操作分出的<=x的树的根
	int Rroot;//>x
};
S split(int x,int k){//在以k为根的树中，把值<=x和>x的节点拆成两棵树
	if(k==0){//没有这个节点
		return S{0,0};
	}
	if(t[k].val<=x){//k应该被分到<=x的树中
		S tmp=split(x,t[k].rc);//递归拆k的右子树，左子树一定在<=x中
		t[k].rc=tmp.Lroot;//认领下面拆出来的<=x的树为右子树
		update(k);//更新size
		return S{k,tmp.Rroot};//返回拆好的两棵子树
	}else{//k应该被分到>x的树中，以下操作基本同上。
		S tmp=split(x,t[k].lc);
		t[k].lc=tmp.Rroot;
		update(k);
		return S{tmp.Lroot,k};
	}
}

这里的update()不重要。

Merge操作

既然把树拆开了，就需要它们缝回去。Merge的作用就是缝合两棵树（保证一棵树中的所有节点的值都比另一棵的节点的值小）。

Merge也通过递归实现。

设\(k_1\)为值较小的树的根节点，\(k_2\)为较大的树的根节点。如果\(k_1\)的键比\(k_2\)小，那\(k_2\)为根的一整棵子树应该全放在\(k_1\)的右子树上。递归缝合到\(k_1\)的右子树上。

如果\(k_1\)的键比\(k_2\)大，\(k_1\)为根的一整棵子树应该放在\(k_2\)的左子树上。同样递归。

举例子，把上面分开的两棵树合并在一起。

每个节点有两个数，第一个是值，第二个是键。

如此操作，即可还原出整棵树。需要注意，如果其中一棵树是空的(\(k=0\))，直接返回另一棵即可。

结果如下。

思路写成代码比较简单。

int merge(int k1,int k2){//把以k1为根的树和k2为根的树缝合在一起
	if(k1==0||k2==0){//如果有一个树不存在，返回另一个即可
		return k1==0?k2:k1;
	}
	if(t[k1].val>t[k2].val){//保证树k1中的所有值都小于等于树k2中的值
		swap(k1,k2);
	}
	if(t[k1].key<t[k2].key){//根k1的键小于根k2，树k2应该整个放在k1的右子树里面
		t[k1].rc=merge(t[k1].rc,k2);//递归处理
		update(k1);//更新size
		return k1;//返回根为t1
	}else{//否则树k1应该放在k2的左子树里
		t[k2].lc=merge(t[k2].lc,k1);
		update(k2);
		return k2;
	}
}

有了Split和Merge，我们就可以开始对Treap大肆蹂躏，完成一些功能了。

插入

为了插入\(x\)，我们把树拆成\(\leq x\)，\(>x\)的两棵，建立一个值为\(x\)的新节点，把结点和\(\leq x\)的合并，整个再和\(>x\)的合并即可。

struct FHQ_Treap{
	void init(int x){//节点初始化，值为x
		key=rand();
		val=x;
		lc=0;
		rc=0;
		size=1;
	}
}
void insert(int x){//插入一个x
	ptr++;
	t[ptr].init(x);//先建好一个节点
	S tmp=split(x,root);//把树分为<=x,>x两部分
	root=merge(merge(tmp.Lroot,ptr),tmp.Rroot);//先把<=x和x缝一起，再整个和>x缝一起即可
	//这里，有可能root会变。
}

删除

把\(\leq x\)的树拆出来，再从里面把\(\leq x-1\)（也就是\(<x\)）的树拿走，剩下的就是全部\(=x\)的树。把根节点的两个儿子互相合并，就会得到一个全新的根。原来的根就被抛弃了，相当于删除。这个操作很巧妙。

void delete(int x){//删除一个x
	S tmp1=split(x,root);
	S tmp2=split(x-1,tmp1.Lroot);
	int Lroot=tmp2.Lroot,Rroot=tmp1.Rroot,mid=tmp2.Rroot;//把树拆成三部分，<x,>x,=x。
	root=merge(merge(Lroot,merge(t[mid].lc,t[mid].rc)),Rroot);//把=x的根的两个子树缝在一起，产生了新根，老的就废了
	//然后再把三部分缝回去
}

查询排名

把\(\leq x-1\)（\(<x\)）的子树拆出来，答案就是\(\leq x-1\)的树的大小+1。所以，需要在插入删除的时候维护大小（使用update()）。

void update(int k){//更新节点size
	t[k].size=(t[k].lc==0?0:t[t[k].lc].size)+(t[k].rc==0?0:t[t[k].rc].size)+1;
}
int rank(int x){//查询x的排名
	S tmp=split(x-1,root);//把<x的子树拆出来
	int ans=t[tmp.Lroot].size;//答案就是子树的size+1，但是因为初始化的时候额外加了一个不应该出现的-INF，所以+1抵消了。
	root=merge(tmp.Lroot,tmp.Rroot);//缝回去
	return ans;
}

这里为什么+1抵消了后面会解释。

查询排名对应的数

使用正常BST的方法即可。

int num(int x){//查询排名为x的数
	x++;//有一个不该出现的-INF
	int k=root;
	while(true){//同正常Treap的思路，从根递归即可。
		if(x-t[t[k].lc].size==1){//如果x就是左子树的大小+1,则这个数就是k的值
			return t[k].val;
		}
		if(x-t[t[k].lc].size<1){//如果小于1，这个数在其左子树中。
			k=t[k].lc;
		}else{//否则在右子树中
			x-=t[t[k].lc].size+1;//在右子树中的排名需要减掉左子树的大小+1（k本身也需要减掉一个）
			k=t[k].rc;
		}
	}
	return 114514;
}

查询前驱

把\(<x\)的子树拆开，一路往右走找最大值就可以。

int pre(int x){//前驱
	S tmp=split(x-1,root);//把<x的子树拆出来，找到子树中的最大值即可
	int k=tmp.Lroot;
	while(t[k].rc!=0){//一直往右边跳
		k=t[k].rc;
	}
	int ans=t[k].val;
	root=merge(tmp.Lroot,tmp.Rroot);
	return ans;
}

查询后继

类似，把\(>x\)的子树拆出来往左找最小值。

int suf(int x){//后继，一个套路
	S tmp=split(x,root);
	int k=tmp.Rroot;
	while(t[k].lc!=0&&t[k].lc!=1){//注意这里，后继不能是-INF，所以k不能是1
		k=t[k].lc;
	}
	int ans=t[k].val;
	root=merge(tmp.Lroot,tmp.Rroot);
	return ans;
}