Treap

Treap

Treap是由Tree和Heap一起组合而成的数据结构，是一种平衡二叉搜索树。每一个数由一个二元组<val, key>表示，其中val表示数的值，而key存储的是一个随机值，Treap对于val来说满足二叉搜索树的性质，对于key来说满足堆的性质(但不满足完全二叉树这一性质)。

为什么二叉搜索树要结合堆的性质呢？在按照1、2、3、4、5这个顺序插入构成一颗二叉搜索树的时候，会退化成一个链表，所以我们给每一个结点加一个随机值，然后随机值满足堆的性质，这样就可以避免最坏情况，使得树基本平衡。

数据结构定义

// val重复的在一个结点记录，由cnt表示， size表示以该结点为根的子树的大小，son[0]表示左儿子，son[1]表示右儿子
struct node {
	int son[2];
	int val, key;
	int cnt, size;
} tree[maxn];

int tot, root;

mt19937 rnd(233);

更新

因为Treap是通过旋转操作来维护树的平衡的，所以需要更新一下结点的size值

void pushup(int p) {
	tree[p].size = tree[tree[p].son[0]].size + tree[tree[p].son[1]].size + tree[p].cnt;
}

旋转

普通的Treap是通过旋转操作来维护树的平衡的，先来了解一下旋转操作吧。

左旋

对A结点进行左旋，以A结点的右儿子为轴，A结点左旋。

右旋

对A结点进行右旋，以A结点的左儿子为轴，A结点右旋。

代码

// d = 0表示左旋，d = 1表示右旋
void rotate(int &p, int d) {
	int k = tree[p].son[d^1];
	tree[p].son[d^1] = tree[k].son[d];
	tree[k].son[d] = p;
	pushup(p);
	pushup(k);
	p = k;
}

插入

void insert(int &p, int x) {
    // 到一个空结点，直接新建一个
	if (!p) {
		p = ++tot;
		tree[p].size = tree[p].cnt = 1;
		tree[p].val = x;
		tree[p].key = rnd();
		return;
	}
    // 找到值相同的结点，直接++cnt和++size就好了
	if (tree[p].val == x) {
		tree[p].size++;
		tree[p].cnt++;
		return;
	}
    // 确定插入到左子树还是右子树
	int d = (x > tree[p].val);
	insert(tree[p].son[d], x);
    // 维护堆的性质，判断是否需要旋转
	if (tree[p].key < tree[tree[p].son[d]].key) rotate(p, d^1);
	pushup(p);
}

删除

void del(int &p, int x) {
    // 找到空结点返回就好
	if (!p) return;
    // 根据二叉搜索树的性质往下找
	if (x < tree[p].val) del(tree[p].son[0], x);
	else if (x > tree[p].val) del(tree[p].son[1], x);
    // 当前节点就是要删除的结点
	else {
        // 如果左右儿子都为空，直接删就好了
		if (!tree[p].son[0] && !tree[p].son[1]) {
			tree[p].cnt--;
			tree[p].size--;
            // 空了就置为0即可
			if (tree[p].cnt == 0) p = 0;
		} else if (tree[p].son[0] && !tree[p].son[1]) {	// 右儿子空
            // 进行右旋，把该节点往下弄
			rotate(p, 1);
			del(tree[p].son[1], x);
		} else if (!tree[p].son[0] && tree[p].son[1]) {	// 左儿子空
            // 进行左旋，把该节点往下弄
			rotate(p, 0);
			del(tree[p].son[0], x);
		} else {
            // 左右都不为空，则把key大的网上弄
			int d = (tree[tree[p].son[0]].key > tree[tree[p].son[1]].key);
			rotate(p, d);
			del(tree[p].son[d], x);
		}
	}
	pushup(p);
}

获取排名

排名定义为比val小的数的个数+1

int getrank(int p, int x) {
	if (!p) return 0;
	if (tree[p].val == x) return tree[tree[p].son[0]].size + 1;
	else if (tree[p].val < x)
		return tree[tree[p].son[0]].size + tree[p].cnt + getrank(tree[p].son[1], x);
	else return getrank(tree[p].son[0], x);
}

根据排名获取值

int getnum(int p, int x) {
	if (!p) return 0;
	if (tree[tree[p].son[0]].size >= x) return getnum(tree[p].son[0], x);
	else if (tree[tree[p].son[0]].size + tree[p].cnt < x)
		return getnum(tree[p].son[1], x - tree[tree[p].son[0]].size - tree[p].cnt);
	else return tree[p].val;
}

获取前驱

前驱是比val小的最大值

int getpre(int p, int x) {
	if (!p) return -inf;
	if (tree[p].val >= x) return getpre(tree[p].son[0], x);
	else return max(tree[p].val, getpre(tree[p].son[1], x));
}

获取后继

后继是比val大的最小值

int getnxt(int p, int x) {
	if (!p) return inf;
	if (tree[p].val <= x) return getnxt(tree[p].son[1], x);
	else return min(tree[p].val, getnxt(tree[p].son[0], x));
}

洛谷P3369

模板题洛谷P3369

// 输入样例
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

// 输出样例
106465
84185
492737

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;


struct node {
	int son[2];
	int val, key;
	int cnt, size;
} tree[maxn];

int tot, root;

mt19937 rnd(233);

void pushup(int p) {
	tree[p].size = tree[tree[p].son[0]].size + tree[tree[p].son[1]].size + tree[p].cnt;
}

void rotate(int &p, int d) {
	int k = tree[p].son[d^1];
	tree[p].son[d^1] = tree[k].son[d];
	tree[k].son[d] = p;
	pushup(p);
	pushup(k);
	p = k;
}

void insert(int &p, int x) {
	if (!p) {
		p = ++tot;
		tree[p].size = tree[p].cnt = 1;
		tree[p].val = x;
		tree[p].key = rnd();
		return;
	}
	if (tree[p].val == x) {
		tree[p].size++;
		tree[p].cnt++;
		return;
	}
	int d = (x > tree[p].val);
	insert(tree[p].son[d], x);
	if (tree[p].key < tree[tree[p].son[d]].key) rotate(p, d^1);
	pushup(p);
}

void del(int &p, int x) {
	if (!p) return;
	if (x < tree[p].val) del(tree[p].son[0], x);
	else if (x > tree[p].val) del(tree[p].son[1], x);
	else {
		if (!tree[p].son[0] && !tree[p].son[1]) {
			tree[p].cnt--;
			tree[p].size--;
			if (tree[p].cnt == 0) p = 0;
		} else if (tree[p].son[0] && !tree[p].son[1]) {
			rotate(p, 1);
			del(tree[p].son[1], x);
		} else if (!tree[p].son[0] && tree[p].son[1]) {
			rotate(p, 0);
			del(tree[p].son[0], x);
		} else {
			int d = (tree[tree[p].son[0]].key > tree[tree[p].son[1]].key);
			rotate(p, d);
			del(tree[p].son[d], x);
		}
	}
	pushup(p);
}

int getrank(int p, int x) {
	if (!p) return 0;
	if (tree[p].val == x) return tree[tree[p].son[0]].size + 1;
	else if (tree[p].val < x)
		return tree[tree[p].son[0]].size + tree[p].cnt + getrank(tree[p].son[1], x);
	else return getrank(tree[p].son[0], x);
}

int getnum(int p, int x) {
	if (!p) return 0;
	if (tree[tree[p].son[0]].size >= x) return getnum(tree[p].son[0], x);
	else if (tree[tree[p].son[0]].size + tree[p].cnt < x)
		return getnum(tree[p].son[1], x - tree[tree[p].son[0]].size - tree[p].cnt);
	else return tree[p].val;
}

int getpre(int p, int x) {
	if (!p) return -inf;
	if (tree[p].val >= x) return getpre(tree[p].son[0], x);
	else return max(tree[p].val, getpre(tree[p].son[1], x));
}

int getnxt(int p, int x) {
	if (!p) return inf;
	if (tree[p].val <= x) return getnxt(tree[p].son[1], x);
	else return min(tree[p].val, getnxt(tree[p].son[0], x));
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i=1; i<=n; i++) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if (opt == 1) insert(root, x);
		else if (opt == 2) del(root, x);
		else if (opt == 3) printf("%d\n", getrank(root, x));
		else if (opt == 4) printf("%d\n", getnum(root, x));
		else if (opt == 5) printf("%d\n", getpre(root, x));
		else printf("%d\n", getnxt(root, x));
	}
	return 0;
}

无旋 Treap

无旋Treap也叫fhq Treap，是由范浩强发明的数据结构，顾名思义，无旋Treap不需要旋转操作便能维护树的平衡，主要是通过分裂和合并两个操作。

数据结构定义

struct node {
	int l, r;
	int val, key;
	int size;
}tree[maxn];

int root, cnt;
mt19937 rnd(233);

int x, y, z;	// 用于分裂时存储树的结点

创建新结点

int newnode(int val) {
	++cnt;
	tree[cnt].val = val;
	tree[cnt].size = 1;
	tree[cnt].key = rnd();
	return cnt;
}

更新

更新操作与普通的Treap相同

void update(int now) {
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

分裂

分裂主要有两种方式

• 按值value分裂，将树分为两颗，一颗树上的val小于等于value，另一棵树大于value
• 按大小sz分裂，将一颗子树分为sz大小，另一颗子树为n-sz大小

这里先讲按值分裂，按大小分裂之后会结合例题看。

假设有下面这样一颗树

我们对它按值17进行分裂，得到的结果如下

// 当前结点序号为now，按照val分裂，分裂成两颗子树，根节点为x和y，因为x和y的值会改变，所以传引用
// 其中以x为根的子树是小于等于val，y为大于val
void split(int now, int val, int &x, int &y) {
    // now为空，则让x和y都为空就好
	if (!now) x = y = 0;
	else {
        // 如果当前结点的值小于等于val，直接让x等于now就好，然后对now的右子树继续分裂
		if (tree[now].val <= val) {
			x = now;
            // 当前结点改为右子树，val不变，x改为x的右子树，y没变化
			split(tree[now].r, val, tree[now].r, y);
		} else {
            // 反之同理，改变左子树
			y = now;
			split(tree[now].l, val, x, tree[now].l);
		}
        // 记得更新结点信息
		update(now);
	}
}

合并

合并操作就是分裂的逆操作，将两颗子树合并为一颗。

// 两颗子树的根为x和y
// 需要注意的是，x子树的值一定一定一定要小于y的值
int merge(int x, int y) {
    // 当有一个为空时，直接返回另一个的值，两个都为空则返回0
	if (!x || !y) return x + y;
    // 通过key来合并，随机化，因为随机，所以这个>号改为>=  < <=都是ok的
	if (tree[x].key > tree[y].key) {
        // y子树一定在x的右边，让x的右子树和y合并，并且更新x右子树的值
		tree[x].r = merge(tree[x].r, y);
		update(x);
		return x;
	} else {
        // 让x和y的左子树合并，并且更新y左子树的值
		tree[y].l = merge(x, tree[y].l);
		update(y);
		return y;
	}
}

插入

// 先按照val进行分裂，其中x子树小于等于val
// 让x和新结点进行合并，再和y子树合并即可
void insert(int val) {
	split(root, val, x, y);
	root = merge(merge(x, newnode(val)), y);
}

删除

// 先按照val进行分裂，分为x和z子树，其中x子树的值小于等于val
// 再将x子树按照val-1进行分裂，分裂成x和y子树，其中x子树的值小于等于val-1，而y子树的值都为val
// 我们删除y子树的根节点，相当于直接让y子树的左子树和右子树合并成y，之后再将x、y、z合并回去即可
void del(int val) {
	split(root, val, x, z);
	split(x, val-1, x, y);
	y = merge(tree[y].l, tree[y].r);
	root = merge(merge(x, y), z);
}

获取排名

// 按照val-1分裂成x和y子树，返回x子树的size+1即可
int getrank(int val) {
	int res;
	split(root, val-1, x, y);
	res = tree[x].size + 1;
	root = merge(x, y);
	return res;
}

根据排名获取值

// 与普通Treap没什么两样
int getnum(int rank) {
	int now = root;
	while (now) {
		if (tree[tree[now].l].size + 1 == rank)
			break;
		else if (tree[tree[now].l].size >= rank)
			now = tree[now].l;
		else {
			rank -= tree[tree[now].l].size + 1;
			now = tree[now].r;
		}
	}
	return tree[now].val;
}

获取前驱

// 将树按照val-1进行分裂，然后返回x子树最右边的值即可
int getpre(int val) {
	split(root, val-1, x, y);
	int now = x;
	while (tree[now].r)
		now = tree[now].r;
	int res = tree[now].val;
	root = merge(x, y);
	return res;
}

获取后继

// 按照val进行分裂，再返回y子树最左边的值
int getnxt(int val) {
	split(root, val, x, y);
	int now = y;
	while (tree[now].l)
		now = tree[now].l;
	int res = tree[now].val;
	root = merge(x, y);
	return res;
}

洛谷P3369

对于上面的模板题，通过无旋Treap的解法如下

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;


struct node {
	int l, r;
	int val, key;
	int size;
}tree[maxn];

int root, cnt;
mt19937 rnd(233);

int x, y, z;

int newnode(int val) {
	++cnt;
	tree[cnt].val = val;
	tree[cnt].size = 1;
	tree[cnt].key = rnd();
	return cnt;
}

void update(int now) {
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

void split(int now, int val, int &x, int &y) {
	if (!now) x = y = 0;
	else {
		if (tree[now].val <= val) {
			x = now;
			split(tree[now].r, val, tree[now].r, y);
		} else {
			y = now;
			split(tree[now].l, val, x, tree[now].l);
		}
		update(now);
	}
}

int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (tree[x].key > tree[y].key) {
		tree[x].r = merge(tree[x].r, y);
		update(x);
		return x;
	} else {
		tree[y].l = merge(x, tree[y].l);
		update(y);
		return y;
	}
}

void insert(int val) {
	split(root, val, x, y);
	root = merge(merge(x, newnode(val)), y);
}

void del(int val) {
	split(root, val, x, z);
	split(x, val-1, x, y);
	y = merge(tree[y].l, tree[y].r);
	root = merge(merge(x, y), z);
}

int getrank(int val) {
	int res;
	split(root, val-1, x, y);
	res = tree[x].size + 1;
	root = merge(x, y);
	return res;
}

int getnum(int rank) {
	int now = root;
	while (now) {
		if (tree[tree[now].l].size + 1 == rank)
			break;
		else if (tree[tree[now].l].size >= rank)
			now = tree[now].l;
		else {
			rank -= tree[tree[now].l].size + 1;
			now = tree[now].r;
		}
	}
	return tree[now].val;
}

int getpre(int val) {
	split(root, val-1, x, y);
	int now = x;
	while (tree[now].r)
		now = tree[now].r;
	int res = tree[now].val;
	root = merge(x, y);
	return res;
}

int getnxt(int val) {
	split(root, val, x, y);
	int now = y;
	while (tree[now].l)
		now = tree[now].l;
	int res = tree[now].val;
	root = merge(x, y);
	return res;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int opt, x;
		scanf("%d%d", &opt, &x);
		if (opt == 1) insert(x);
		else if (opt == 2) del(x);
		else if (opt == 3) printf("%d\n", getrank(x));
		else if (opt == 4) printf("%d\n", getnum(x));
		else if (opt == 5) printf("%d\n", getpre(x));
		else printf("%d\n", getnxt(x));
	}
	return 0;
}

无旋Treap维护区间信息

无旋Treap还能和线段树那样维护区间信息，结合例题来看

洛谷P3391

// 样例输入
5 3
1 3
1 3
1 4

// 样例输出
4 3 2 1 5

对于这种反转问题，暴力去翻肯定是会超时的，结合线段树lazy tag的思想，通过标记区间翻转标记，来降低时间复杂度。为了解决这个问题，无旋Treap将按大小进行分裂

数据结构定义

struct node {
	int l, r;
	int val, key;
	int size;
	int reverse;	// 翻转标记
}tree[maxn];

int cnt, root;
mt19937 rnd(233);
int x, y, z;

标记下传

因为Treap在分裂和合并的时候，有可能改变结点的位置，所以我们需要将reverse标记下传，以防丢失信息

void pushdown(int now) {
	swap(tree[now].l, tree[now].r);
	tree[tree[now].l].reverse ^= 1;
	tree[tree[now].r].reverse ^= 1;
	tree[now].reverse = 0;
}

分裂

void split(int now, int sz, int &x, int &y) {
	if (!now) x = y = 0;
	else {
        // 标记下传
		if (tree[now].reverse) pushdown(now);
        // 左子树不足sz那么多，要往右子树继续分裂
		if (tree[tree[now].l].size < sz) {
			x = now;
			split(tree[now].r, sz - tree[tree[now].l].size - 1, tree[now].r, y);
		} else {
			y = now;
			split(tree[now].l, sz, x, tree[now].l);
		}
		update(now);
	}
}

合并

// 分裂只需要加一步标记下传即可
int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (tree[x].key < tree[y].key) {
		if (tree[x].reverse) pushdown(x);
		tree[x].r = merge(tree[x].r, y);
		update(x);
		return x;
	} else {
		if (tree[y].reverse) pushdown(y);
		tree[y].l = merge(x, tree[y].l);
		update(y);
		return y;
	}
}

反转

// 将树按照l-1大小进行分裂，其中y子树的大小为n-l+1
// 再将y子树按照r-l+1大小进行分裂，分裂出来的y子树就是我们需要反转的区间，改变标记即可
void reverse(int l, int r) {
	int x, y, z;
	split(root, l-1, x, y);
	split(y, r-l+1, y, z);
	tree[y].reverse ^= 1;
	root = merge(merge(x, y), z);
}

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e5+5;

struct node {
	int l, r;
	int val, key;
	int size;
	int reverse;
}tree[maxn];

int cnt, root;
mt19937 rnd(233);
int x, y, z;

int newnode(int val) {
	++cnt;
	tree[cnt].val = val;
	tree[cnt].size = 1;
	tree[cnt].key = rnd();
	return cnt;
}

void update(int now) {
	tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;
}

void pushdown(int now) {
	swap(tree[now].l, tree[now].r);
	tree[tree[now].l].reverse ^= 1;
	tree[tree[now].r].reverse ^= 1;
	tree[now].reverse = 0;
}

void split(int now, int sz, int &x, int &y) {
	if (!now) x = y = 0;
	else {
		if (tree[now].reverse) pushdown(now);
		if (tree[tree[now].l].size < sz) {
			x = now;
			split(tree[now].r, sz - tree[tree[now].l].size - 1, tree[now].r, y);
		} else {
			y = now;
			split(tree[now].l, sz, x, tree[now].l);
		}
		update(now);
	}
}

int merge(int x, int y) {
	if (!x || !y) return x + y;
	if (tree[x].key < tree[y].key) {
		if (tree[x].reverse) pushdown(x);
		tree[x].r = merge(tree[x].r, y);
		update(x);
		return x;
	} else {
		if (tree[y].reverse) pushdown(y);
		tree[y].l = merge(x, tree[y].l);
		update(y);
		return y;
	}
}

void reverse(int l, int r) {
	int x, y, z;
	split(root, l-1, x, y);
	split(y, r-l+1, y, z);
	tree[y].reverse ^= 1;
	root = merge(merge(x, y), z);
}

void print(int now) {
	if (!now) return;
	if (tree[now].reverse) pushdown(now);
	print(tree[now].l);
	printf("%d ", tree[now].val);
	print(tree[now].r);
}

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++)
		root = merge(root, newnode(i));
	while (m--) {
		int l, r;
		scanf("%d%d", &l, &r);
		reverse(l, r);
	}
	print(root);
	printf("\n");
	return 0;
}