FHQ-Treap（非旋 Treap）学习笔记

时间 2020-07-21 标签 fhq treap 非旋 treap 学习笔记

参考文章

因此我这个学习笔记。。就是抄一遍？由于他讲的太清楚了！node

那这篇学习笔记存在的意义是？学习笔记嘛，一方面也是写给本身看的。。c++

Treap

Treap = BST + Heap，什么意思？web

一开始每一个节点都具备一个权值 val，如今咱们给每一个节点都增长一个修正值 key，使得 Treap 在关注 val 时是 BST（二叉搜索树），在关注 key 时是 Heap（堆），这个堆须要知足每一个节点严格小于全部子树里的儿子（也就是说这里是小根堆）。能够证实，给定一些点的集合，构成的 Treap 只可能有一个，且当 key 随机时树高指望 $O(\log n)$ 。app

FHQ-Treap 的基本操做

FHQ-Treap 给出了一种不基于旋转的维护方法，其本质是依靠 Treap 的结构惟一性。svg

~~FHQ-Treap 我吹爆，实在是太好写了~~学习

分裂

有两种分裂方式，看具体要作什么问题。spa

按权值分裂

咱们要作的事：给定一个 Treap，将其中全部节点按照是否小于等于 queryval 分类，分别分裂进两个不一样的 Treap。code

借用参考文章的一张图。。xml

咱们动态维护两棵要造的 Treap 的虚点 x, y（这两个虚点也能表示这两棵 Treap 自己，故下文不会区分了）和原 Treap 上的点 now，经过判断 val[now] 与 queryval 的大小来判断左右子树的归属，并递归到儿子中继续分裂。

好比若是 val[now]<=queryval，那么{左子树+now}（也就是第2步中蓝色部分）都将归属 x，将这一部分拷过去后虚点 x 前往右儿子，now 也前往右儿子。

实现：

void split(int now, int k, int& x, int& y) { // 注意 x,y 是传址
	if (!now) { x = y = 0; return; }
	if (val[now] <= k) x = now, split(rs[now], k, rs[now], y); // x = now 是拷贝过去，递归进入下一层继续分裂
	else y = now, split(ls[now], k, x, ls[now]); // {右子树+now} 被拷贝到 y
	pushUp(now); // 上传信息，在下面【按排名分裂】会提到
}

按排名分裂

这里的排名指的是中序遍历（左中右）的排名。

功能：将排名 <= k 的放到 x 里，>k 的放到 y 里。

咱们只须要算出 now 的 “val” 是多少，若是是按排名分裂，这个 “val” 就是 siz[ls[now]]+1 了。

那么首先咱们须要维护每一个点的子树大小 siz，这能够经过上传标记完成：

void pushUp(int x) { siz[x] = siz[ls[x]] + siz[rs[x]] + 1; }

接下来在写的时候咱们须要关注何时加 pushUp，好比按排名分裂的实现：

void split(int now, int k, int& x, int& y) {
	if (!now) { x = y = 0; return; }
	if (siz[ls[now]] + 1 <= k) x = now, split(rs[now], k - siz[ls[now]] - 1, rs[now], y);
	else y = now, split(ls[now], k, x, ls[now]);
	pushUp(now);
}

合并

给两个 Treap 咱们就合并这行不通的，但咱们能够作的是：给定两个 Treap x, y 并保证 y 的全部点的 val 都大于等于 x 全部点的 val，将它们合并成一个 Treap。能够发现这个功能是随分裂而生的，由于分裂出来的两个 Treap 正好知足上述条件。

仍是~~厚颜无耻地~~借用一下参考文章里的图。。

如图，咱们沿用了上文分裂的例子，黑底白字是 val 权值，而白底黑字是 key 修正值。当一个节点被染蓝，说明此节点已被放入最终得到了主树内。（摘自参考文章）

咱们要同时维护 val 的二叉树性质和 rnd 的小根堆性质。令 merge(x,y) （两个参数 x,y 既能够被理解为点，也能够被理解为它做为根所表明的 Treap）表示将 x,y 两棵 Treap 合并，返回合并后的根。能够肯定的是根是 x,y 中的其中一个，因此咱们比较 key 来判断谁是根。

int merge(int x, int y) { 
	if (!x || !y) return x + y;
	if (key[x] < key[y]) { rs[x] = merge(rs[x], y), pushUp(x); return x; } // 根是 x，y 确定接在 rs[x] 里面。
	else { ls[y] = merge(x, ls[y]), pushUp(y); return y; } // 根是 y，x 确定接在 ls[y] 里面。
}

那么 FHQ-Treap 最重要的两个操做就讲完了。

FHQ-Treap 维护集合操做 - 引例 [模板]普通平衡树

题意

连接

插入

咱们将 Treap 分裂成 <=x 和 >x 的，而后新建一个权值为 x 的节点（也就是一棵大小为 1 的 Treap），将三者按序合并便可。

void insert(int x) { r1 = r2 = 0, split(root, x, r1, r2), root = merge(merge(r1, newnode(x)), r2); }

删除

咱们将 Treap 分裂成三部分：<x，=x，>x，而后在 =x 中把根去掉（也就是把根的左右子合并），再将三部分合并便可。

void remove(int x) {
	r1 = r2 = r3 = 0, split(root, x, r1, r2), split(r1, x - 1, r1, r3); //r1(<x),r3(=x),r2(>x)
	r3 = merge(ls[r3], rs[r3]), root = merge(merge(r1, r3), r2);
}

求排名

咱们将 Treap 分裂成 <x 和 >=x，直接查 <x 的大小就可。

int rnk(int x) {
	int ret = 0; r1 = r2 = 0, split(root, x - 1, r1, r2), ret = siz[r1] + 1, root = merge(r1, r2);
	return ret;
}

求第 k 大

按照正常的 BST 搜索便可。

int kth(int x, int k) {
	if (k <= siz[ls[x]]) return kth(ls[x], k);
	else if (k > siz[ls[x]] + 1) return kth(rs[x], k - siz[ls[x]] - 1);
	else return x;
}

求前驱 / 后继

前驱：将 Treap 分为两部分：<x，>=x，找到 <x 中最大的（也就是从根开始一直往右走）便可。

后继：同理。

int pre(int x) {
	split(root, x - 1, r1, r2); int p;
	for (p = r1; rs[p]; p = rs[p]);
	root = merge(r1, r2); return p;
}
int nex(int x) {
	split(root, x, r1, r2); int p;
	for (p = r2; ls[p]; p = ls[p]);
	root = merge(r1, r2); return p;
}

完整代码

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

typedef long long ll;
const int MAXN = 100005;

int N, root, ls[MAXN], rs[MAXN], val[MAXN], key[MAXN], siz[MAXN], Tlen;
int newnode(int x) { ++Tlen, val[Tlen] = x, key[Tlen] = rand(), siz[Tlen] = 1; return Tlen; }
void pushUp(int x) { siz[x] = siz[ls[x]] + siz[rs[x]] + 1; }
void split(int now, int k, int& x, int& y) {
	if (!now) { x = y = 0; return; }
	if (val[now] <= k) x = now, split(rs[now], k, rs[now], y);
	else y = now, split(ls[now], k, x, ls[now]);
	pushUp(now);
}
int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (key[x] > key[y]) { rs[x] = merge(rs[x], y), pushUp(x); return x; }
	else { ls[y] = merge(x, ls[y]), pushUp(y); return y; }
}
int r1, r2, r3;
void insert(int x) { r1 = r2 = 0, split(root, x, r1, r2), root = merge(merge(r1, newnode(x)), r2); }
void remove(int x) {
	r1 = r2 = r3 = 0, split(root, x, r1, r2), split(r1, x - 1, r1, r3), r3 = merge(ls[r3], rs[r3]), root = merge(merge(r1, r3), r2);
}
int rnk(int x) {
	int ret = 0; r1 = r2 = 0, split(root, x - 1, r1, r2), ret = siz[r1] + 1, root = merge(r1, r2);
	return ret;
}
int kth(int x, int k) {
	if (k <= siz[ls[x]]) return kth(ls[x], k);
	else if (k > siz[ls[x]] + 1) return kth(rs[x], k - siz[ls[x]] - 1);
	else return x;
}
int pre(int x) {
	split(root, x - 1, r1, r2); int p;
	for (p = r1; rs[p]; p = rs[p]);
	root = merge(r1, r2); return p;
}
int nex(int x) {
	split(root, x, r1, r2); int p;
	for (p = r2; ls[p]; p = ls[p]);
	root = merge(r1, r2); return p;
}

int main() {
	scanf("%d", &N); int op, x;
	srand(19260817);
	for (int i = 1; i <= N; ++i) {
		scanf("%d%d", &op, &x);
		if (op == 1) insert(x);
		else if (op == 2) remove(x);
		else if (op == 3) printf("%d\n", rnk(x));
		else if (op == 4) printf("%d\n", val[kth(root, x)]);
		else if (op == 5) printf("%d\n", val[pre(x)]);
		else if (op == 6) printf("%d\n", val[nex(x)]);
	}
	return 0;
}

FHQ-Treap 维护区间操做 - 引例 [模板]文艺平衡树

题意

连接

怎么维护

咱们令 Treap 表示的序列是它的中序遍历所构成的序列。

若是咱们要求区间和，咱们只须要将 Treap 按排名把 l<=排名<=r 这一部分分出来，而后求区间和（在每一个点上维护区间和的值而后 pushup）

若是咱们要输出整个序列，咱们只须要跑中序遍历。

若是咱们要插入，咱们只须要用上面【维护集合操做】中的插入方法来插入。

懒惰标记

但这题的翻转操做怎么维护？使用懒惰标记。

但这已经在线段树给讲透了？因此好像也没啥可讲的。

完整代码

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

const int MAXN = 100005;
int N, M, root, ls[MAXN], rs[MAXN], val[MAXN], key[MAXN], siz[MAXN], tag[MAXN], Tlen;
int newnode(int x) { ++Tlen, val[Tlen] = x, key[Tlen] = rand(), siz[Tlen] = 1; return Tlen; }
void pushUp(int x) { siz[x] = siz[ls[x]] + siz[rs[x]] + 1; }
void cover(int x) { tag[x] ^= 1, swap(ls[x], rs[x]); }
void pushDown(int x) { if (tag[x]) cover(ls[x]), cover(rs[x]), tag[x] = 0; }
void split(int now, int k, int& x, int& y) {
	if (!now) { x = y = 0; return; }
	pushDown(now);
	if (siz[ls[now]] + 1 <= k) x = now, split(rs[now], k - siz[ls[now]] - 1, rs[now], y);
	else y = now, split(ls[now], k, x, ls[now]);
	pushUp(now);
}
int merge(int x, int y) {
	if (!x || !y) return x + y;
	pushDown(x), pushDown(y);
	if (key[x] < key[y]) { ls[y] = merge(x, ls[y]), pushUp(y); return y; }
	else { rs[x] = merge(rs[x], y), pushUp(x); return x; }
}
void modify(int l, int r) {
	int r1 = 0, r2 = 0, r3 = 0;
	split(root, r, r1, r2), split(r1, l - 1, r1, r3), cover(r3);
	root = merge(merge(r1, r3), r2);
}
void dfs(int x) {
	pushDown(x);
	if (ls[x]) dfs(ls[x]);
	printf("%d ", val[x]);
	if (rs[x]) dfs(rs[x]);
}

int main() {
	scanf("%d%d", &N, &M); int l, r;
	srand(19260817);
	for (int i = 1; i <= N; ++i) root = merge(root, newnode(i));
	while (M--) {
		scanf("%d%d", &l, &r), modify(l, r);
	}
	dfs(root);
	return 0;
}

例题

[BJOI2017] 喷施水战改

FHQ-Treap（非旋 Treap） 学习笔记

参考文章

Treap

FHQ-Treap 的基本操做

分裂

按权值分裂

按排名分裂

合并

FHQ-Treap 维护集合操做 - 引例 [模板]普通平衡树

题意

插入

删除

求排名

求第 k 大

求前驱 / 后继

完整代码

FHQ-Treap 维护区间操做 - 引例 [模板]文艺平衡树

题意

怎么维护

懒惰标记

完整代码

例题

FHQ-Treap（非旋 Treap）学习笔记