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

FHQ-Treap 详解

时间：2023-08-07 12:33:26浏览次数：41  
标签：return treap int root Treap 详解 merge FHQ

目录

1）FHQ-Treap 基本功能理论与实现

不同于经典的基于左旋、右旋的 Treap，FHQ-Treap 是基于分裂与合并的的一种 Treap。虽然两者操作方式完全不同，但产生的结果是一样的。而且，FHQ-Treap 具有好写（打板子超快）、好理解（左旋右旋我到现在还没搞明白）以及可持久化、区间翻转、移动等等一大坨优点。

接下来会详细介绍 FHQ-Treap。

1.1）FHQ-Treap 模型

首先，它是一个 Treap；其次，它是一个基于分裂+合并的 Treap。

比如，可以通过创建一个只有根节点的 Treap，然后再和原来的 Treap 合并，这就是插入节点。

再比如，可以通过分裂开 Treap，把某个节点分离开，合并其他的节点，这就是删除节点。

……如此好用、好理解的 FHQ-Treap 如何实现呢？

Treap 的话就不多说了，可以参考上面的博客；那么如何在分裂+合并操作中维护这个 Treap 呢？

众所周知，Treap 要维护的无非两点：

  1. 键值（key），满足 \(左儿子键值 \leq 该节点键值 \leq 右儿子键值\)

  2. 优先级（pri），满足 \(左儿子优先级或右儿子的优先级 \leq 该节点的优先级\)

我们需要在分裂操作与合并操作中根据这两点对 Treap 进行维护（因为其他操作都建立在这两个操作上）。

我们定义一个结构体，记录 Treap 上每个点的信息。

struct Node {
	int lsn,rsn;
	int key,pri,siz;
};
int tSize=0,root=0;
Node treap[MS];

其中 tSize 是节点个数，root 是 Treap 的根。这里使用了数组的方式存储 Treap。

1.2）操作一：分裂（Split）

Split 需要考虑四个参数，分别是当前遍历到的节点、分裂的标准、传递回的两棵树的根。

一般，Split 都是讲某个 Treap 分裂成一个小于等于某值的 Treap，一个大于该值的 Treap。

void split(int u,int x,int &L,int &R);

其中很妙的一点，\(L\) 与 \(R\) 都传递了它的地址，即可通过该操作修改某个 Treap 的左子树、右子树信息或传递回分裂开的两个 Treap 的编号。这一点在后面的应用中十分重要。

那么如何分裂呢？

（这里分裂的操作并不用到优先级，节点上的值都是键值）

很明显的可以看出：

  • 当目前枚举到的 Treap 的根要小于等于分裂标准时，其左子树都必然小于等于分裂标准，只用考虑右子树；

  • 反之，当目前 Treap 的根要大于分裂标准是，其右子树必然都大于分裂标准，只用考虑左子树。

所以，代码就很明显了：

void split(int u,int x,int &L,int &R) {
	if(u==0) {
		L=R=0;
		return ;
	}
	if(treap[u].key<=x) L=u,split(treap[u].rsn,x,treap[u].rsn,R);
	else R=u,split(treap[u].lsn,x,L,treap[u].lsn);
	updateRoot(u);
	return ;
}

由于 Split 的时间复杂度就是树高，所以它的期望时间复杂度为 \(\mathcal{O}(\log_2^n)\)

1.3）操作二：合并（Merge）

划重点：Merge 的性质：Merge 要满足合并的两个 Treap （用根 L 与 R 表示），L 中的值都小于等于 R！

合并的时候，就要考虑优先值了。先比较两颗 Treap 的根节点的优先值大小。如果 L 大，把 R 合并到 L 的右子树上去；否则，把 L 合并到 R 的左子树上去（因为 L 中的值都小于 R）。最终，Merge 要返回合并后的根。

int merge(int L,int R) {
	if(L==0||R==0) return L+R;
	if(treap[L].pri>treap[R].pri) {
		treap[L].rsn=merge(treap[L].rsn,R);
		updateRoot(L);
		return L;
	}
	else {
		treap[R].lsn=merge(L,treap[R].lsn);
		updateRoot(R);
		return R;
	}
}

顺便说一下 updateRoot。用来更新某个节点为根的 Treap 的大小（求排名什么的要用到）。

void updateRoot(int u) {
	treap[u].siz=treap[treap[u].lsn].siz+treap[treap[u].rsn].siz+1;
	return ;
}

同上，期望时间复杂度 \(\mathcal{O}(\log_2^n)\)

\(P.S.\) 到目前为止，FHQ-Treap 最难的部分都已经被你搞明白啦！剩下的都很简单的啦！

1.4）操作三：插入新节点

这很简单，首先创建一个只有一个节点的 Treap：

void makeNewNode(int x) {
	++tSize;
	treap[tSize].siz=1;
	treap[tSize].lsn=treap[tSize].rsn=0;
	treap[tSize].key=x,treap[tSize].pri=rand();
	return ;
}

再把这个 Treap 合并到大 Treap 上：（注意 Merge 的性质，所以要先分裂）

int insert(int x) {
	int L,R;
	split(root,x,L,R);
	makeNewNode(x);
	root=merge(merge(L,tSize),R);
	return tSize;
}

1.5）删除某个节点

这里假设只删除一个与查询的值相通的节点。

先分裂出一颗全是要删除的值的 Treap，然后把这个 Treap 的左子树与右子树进行合并（把根丢掉），实现该操作。

int delNum(int x) {
	int L,M,R;
	split(root,x,L,R);
	split(L,x-1,L,M);
	M=merge(treap[M].lsn,treap[M].rsn);
	root=merge(merge(L,M),R);
	return root;
}

当然，如果你要一次性删除所有值为 \(x\) 的节点，可以这么写：

int delNum(int x) {
	int L,M,R;
	split(root,x,L,R);
	split(L,x-1,L,M);
	root=merge(L,R);
	return root;
}

1.6）查询某个值的排名

不说了，把小于 \(x\) 的分裂出来，它的大小加一。

int getRank(int x) {
	int L,R,res;
	split(root,x-1,L,R);
	res=treap[L].siz+1;
	root=merge(L,R);
	return res;
}

1.7）查询排名为 \(k\) 的值

很好理解。

int kth(int u,int k) {
	if(k==treap[treap[u].lsn].siz+1) return u;
	if(k<=treap[treap[u].lsn].siz) return kth(treap[u].lsn,k);
	return kth(treap[u].rsn,k-treap[treap[u].lsn].siz-1);
}

1.8）查询 \(x\) 的前驱与后继

见代码。

// 前驱
int precursor(int x) {
	int L,R,res;
	split(root,x-1,L,R);
	res=treap[kth(L,treap[L].siz)].key;
	root=merge(L,R);
	return res;
}
// 后继
int successor(int x) {
	int L,R,res;
	split(root,x,L,R);
	res=treap[kth(R,1)].key;
	root=merge(L,R);
	return res;
}

1.9）End of this unit

以上就是所有 FHQ-Treap 的基本操作，接下来讲几个应用。

2）FHQ-Treap 的应用

2.1）洛谷 P3369

不说，套板子：

#include <bits/stdc++.h>
using namespace std;

int n;
const int MS=100005;
struct Node {
	int lsn,rsn;
	int key,pri,siz;
};
int tSize=0,root=0;
Node treap[MS];
void makeNewNode(int x) {
	++tSize;
	treap[tSize].siz=1;
	treap[tSize].lsn=treap[tSize].rsn=0;
	treap[tSize].key=x,treap[tSize].pri=rand();
	return ;
}
void updateRoot(int u) {
	treap[u].siz=treap[treap[u].lsn].siz+treap[treap[u].rsn].siz+1;
	return ;
}
void split(int u,int x,int &L,int &R) {
	if(u==0) {
		L=R=0;
		return ;
	}
	if(treap[u].key<=x) L=u,split(treap[u].rsn,x,treap[u].rsn,R);
	else R=u,split(treap[u].lsn,x,L,treap[u].lsn);
	updateRoot(u);
	return ;
}
int merge(int L,int R) {
	if(L==0||R==0) return L+R;
	if(treap[L].pri>treap[R].pri) {
		treap[L].rsn=merge(treap[L].rsn,R);
		updateRoot(L);
		return L;
	}
	else {
		treap[R].lsn=merge(L,treap[R].lsn);
		updateRoot(R);
		return R;
	}
}
int insert(int x) {
	int L,R;
	split(root,x,L,R);
	makeNewNode(x);
	root=merge(merge(L,tSize),R);
	return tSize;
}
int delNum(int x) {
	int L,M,R;
	split(root,x,L,R);
	split(L,x-1,L,M);
	M=merge(treap[M].lsn,treap[M].rsn);
	root=merge(merge(L,M),R);
	return root;
}
int getRank(int x) {
	int L,R,res;
	split(root,x-1,L,R);
	res=treap[L].siz+1;
	root=merge(L,R);
	return res;
}
int kth(int u,int k) {
	if(k==treap[treap[u].lsn].siz+1) return u;
	if(k<=treap[treap[u].lsn].siz) return kth(treap[u].lsn,k);
	return kth(treap[u].rsn,k-treap[treap[u].lsn].siz-1);
}
int precursor(int x) {
	int L,R,res;
	split(root,x-1,L,R);
	res=treap[kth(L,treap[L].siz)].key;
	root=merge(L,R);
	return res;
}
int successor(int x) {
	int L,R,res;
	split(root,x,L,R);
	res=treap[kth(R,1)].key;
	root=merge(L,R);
	return res;
}

int main() {
	scanf("%d",&n);
	while(n--) {
		int opt,x;
		scanf("%d%d",&opt,&x);
		if(opt==1) insert(x);
		if(opt==2) delNum(x);
		if(opt==3) printf("%d\n",getRank(x));
		if(opt==4) printf("%d\n",treap[kth(root,x)].key);
		if(opt==5) printf("%d\n",precursor(x));
		if(opt==6) printf("%d\n",successor(x));
	}
	return 0;
}

END

还有几个应用没更新……我懒狗，等以后吧

标签：return,treap,int,root,Treap,详解,merge,FHQ
From： https://www.cnblogs.com/TimelessWelkinBlog/p/17610065.html

相关文章

  • php://input输入流详解
    php://input输入流详解对于php://input介绍，PHP官方手册文档有一段话对它进行了很明确地概述。php://inputallowsyoutoreadrawPOSTdata.Itisalessmemoryintensivealternativeto$HTTP\_RAW\_POST_DATAanddoesnotneedanyspecialphp.inidirectives.php://in......
  • $_SERVER 全局变量内容详解
    echo"<h1>服务器</h1>";//**********************  服务器  *********************echo $_SERVER['SERVER_NAME']."<br />";     //服务器的名称echo $_SERVER['SERVER_ADDR']."<br />";     //服务器的ipecho ......
  • 详解Nodejs中的Process对象
    在Nodejs中，process是一个全局对象，它提供了与当前进程和运行时环境交互的方法和属性。通过process对象，我们可以访问进程的信息、控制流程和进行进程间通信，这些都是服务端语言应该具备的能力。本文将全面介绍process对象的使用场景，从基础概念到高级应用，带有代码示例，让您深入了解它的......
  • 详解直播应用源码Android端优质技术（三）：可变比特率
     直播应用源码平台作为如今一个火爆的平台深受现代人的喜爱，而直播行业也是流行的媒体形式之一，所以不论是直播应用源码的观众用户还是作为直播应用源码的主播用户人数都是巨大的，并且用户地区涵盖了世界各个国家。这时候，直播应用源码平台就需要开发技术来去提高平台的稳定，提升平台......
  • 详解直播应用源码Android端优质技术（三）：可变比特率
    直播应用源码平台作为如今一个火爆的平台深受现代人的喜爱，而直播行业也是流行的媒体形式之一，所以不论是直播应用源码的观众用户还是作为直播应用源码的主播用户人数都是巨大的，并且用户地区涵盖了世界各个国家。这时候，直播应用源码平台就需要开发技术来去提高平台的稳定，提升平台的质......
  • linux启动服务配置详解
    init进程是所有进程的发起者和控制者。因为在任何基于Unix的系统(比如 linux)中，它都是第一个运行的进程，所以init进程的编号(ProcessID，PID)永远是1。如果init出现了问题，系统的其余部分也就随之而垮掉了。init服务init进程是所有进程的发起者和控制者。因为......
  • 【开发中】Git常用命令详解
    基于平时工作的场景，整理了使用频率较高的一些命令和参数，作为一个Git命令的备忘录。gitclone概述：将远程Git仓库克隆到本地，自动将远程仓库的所有分支和历史记录复制到本地。格式：gitclone[-b<name>]<repository>[<directory>]参数：-b<name>，等同--branch<name>不将新创......
  • docker pull 镜像拉取命令详解
    Docker是一种流行的容器化平台，它允许用户构建、分享和运行容器化的应用程序。要使用Docker，您需要先下载所需的Docker镜像。之前我们介绍了在Ubuntu系统上安装docker，本文将接着介绍如何使用DockerPull命令下载Docker镜像的步骤。dockerpulldockerpull命令是用于从镜像仓库中拉取......
  • docker镜像管理命令详解
    Docker是一种流行的容器化平台，它允许用户构建、分享和运行容器化的应用程序。在Docker中，镜像是构建和创建容器的基础。之前的文章我们介绍了docker安装还有docker镜像的拉取，本文将介绍一些常用的Docker镜像管理命令，帮助我们管理和操作Docker镜像。dockerimagesdockerimages可以查......
  • 【C语言】操作符详解（一）
    1.原码，反码，补码inta=1;整形占用四个字节----32bit00000000000000000000000000000001 (数值位)1.1原码，反码，补码的介绍整数的2进制表示方法有三种，即原码，反码，补码三种表⽰⽅法均有符号位和数值位两部分，符号位都是⽤0表⽰“正”，⽤1表⽰“负”，⽽数值位最⾼位的⼀位是被当做符号位，......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99