【学习】fhq-treap

fhq-treap 是一种好写、复杂度低，且功能的优秀数据结构，涵盖了 treap 几乎所有的功能，其巧妙之处，就在于运用分离和合并两种操作代替了旋转操作。

1. BST 的定义

（摘自 OI Wiki）二叉搜索树（BST）是一种二叉树的树形数据结构，其定义如下：

• 空树是 BST
• 若 BST 左子树不为空，则其左子树上所有点的附加权值均小于根节点。
• 若 BST 右子树不为空，则其右子树上所有点的附加权值均大于根节点。
• BST 的左右子树均为 BST。

2. fhq-treap

2.1 需要存储的信息

左儿子 ls，右儿子 rs，子树大小 sz，权值 val 维护 tree 的性质，及随机优先级 key 维护 heap 的性质。

大体同 treap 相同，但 fhq-treap 不需要记录 val 重复次数 cnt，因为一般情况下，它不将权值相同节点视作一个节点。

2.2 更新答案 sz[x] = sz[ls[x]] +服务器托管网 sz[rs[x]] + 1;

2.3 基础操作：分裂、合并与新建节点

2.3.1 分裂 split

1. 按照权值大小分裂

将原树 (T) 分成左右两个子树 (T_l), (T_r)。设当前节点为 (p):

当 (p=0) 时停止 split。

void split(int p, int v, int &x, int &y) {
  if (!p) {x = y = 0; return ;}
  if (val[p] 

2. 按照子树大小分裂

同理。

void split(int p, int v, int &x, int &y) {
  if (!p) {x = y = 0; return服务器托管网 ;}
  if (v 

2.3.2 合并 merge

条件：合并的两棵树 (T_x) 和 (T_y) 必须满足一棵严格小于另一棵，此处设 (T_x。

当 (x,y) 不全非空停止 merge，使用类似线段树合并 trick，返回 (x or y)

int merge(int x, int y) {
  if (!x || !y) return x | y;
  if (key[x] 

2.3.1 新建节点

int nd(int v) {
  int x = node++;
  val[x] = v, rd[x] = rand(), sz[x] = 1;
  return x;
}

2.4 更多基础功能

见普通平衡树模板题 P3369 【模板】普通平衡树

#include 
using namespace std;
const int N = 1e5 + 5, inf = 1e9 + 7;
int n, m, rt, node, ls[N], rs[N], val[N], rd[N], sz[N];
void push(int x) {sz[x] = sz[ls[x]] + sz[rs[x]] + 1;}
void spl(int p, int v, int &x, int &y) {
	if (!p) {x = y = 0; return ;}
	if (val[p] = val[p]) p = rs[p];
		else ans = val[p], p = ls[p];
	}
}
int rnk(int v) {
	int x = 0, y = 0, ans = 0;
	spl(rt, v - 1, x, y), ans = sz[x] + 1;
	return rt = mer(x,y), ans;
}
int main(){
	cin >> n;
	while (n--) {
		int op, x;
		cin >> op >> x;
		if (op == 1) ins(x);
		else if (op == 2) del(x);
		else if (op == 3) cout 

学习资料：

1. fhq-treap by Alex_Wei

2. fhq-treap by 粉兔

3. OI Wiki

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Android应用程序架构

Android Application Architecture 我们从标准活动和AsyncTasks到由RxJava支持的基于MVP的现代架构的旅程。 Android开发生态系统变得非常快。每周都会创建新工具，更新Lib，写博客文章和发言。如果你去度假一个月…