FHQ-Treap 学习笔记

Treap = Tree + Heap.

Treap 是一种弱平衡二叉树，可以看作是笛卡尔树：其每个点有一个二元组 \((Key, Value)\)，\(Key\) 满足二叉搜索树的性质，而 \(Value\) 满足堆的性质（一般是小根堆）。其中 \(Key\) 是我们实际用到的信息，而 \(Value\) 则是一个随即的权值，用来保证其期望高度为 \(\log n\)。

旋转 Treap 通过旋转操作来维护其性质，而无旋 Treap，即 FHQ-Treap 则通过分裂合并的方式来实现。

分裂（Split）

功能：将一棵 Treap 按照一个值 \(k\) 分裂成两棵，第一棵的所有 \(Key\) 都 \(< k\)，第二课的所有 \(Key\) 都 \(\ge k\)。

考虑当前这棵 Treap 的根节点，如果其 \(Key < k\)，那么他以及他的左子树一定都在第一棵 Treap 里，而右子树又变成了一个子问题，只要分裂好之后将第一棵 Treap 的根作为当前节点的右儿子即可。
当前节点 \(Key \ge k\) 同理，当前节点及其右子树都在第二棵 Treap 中，递归处理左儿子，将其分裂出来的第二棵 Treap 的根作为当前节点的左儿子即可。
当这棵树为空的时候则不需要分裂了，直接返回空节点即可。

具体实现时可以使用传实参的方法。代码如下：

void split(int now,int k,int &u,int &v) {
    if (now==0) {u=v=0;return ;}// 空节点
    if (key[now]<k) u=now,split(rs[now],k,rs[now],v);// 根节点在第一棵 Treap 中
    else v=now,split(ls[now],k,u,ls[now]);// 根节点在第二棵 Treap 中
    push_up(now);// 由于分裂会导致树的形态变化（合并也会），所以要 push_up（类似于线段树）保证节点信息（如子树大小等）正确。
    return ;
}

合并（Merge）

功能：合并两棵 Treap，前提是第一棵 Treap 的所有 \(Key\) 都小于等于第二棵 Treap 的任意 \(Key\)。

考虑当前两棵 Treap 的根，若第一棵树的根的 \(Value\) 更小，则让其作为合并后 Treap 的根，其左子树不变，于是变成了右子树与第二棵 Treap 合并。
第二棵树的根的 \(Value\) 更小同理，递归合并第一棵树和第二棵树的左子树即可。
当某一棵树为空的时候直接返回另一棵树即可。

代码如下：

int merge(int u,int v) {// 返回值为合并后根的编号。
    if (u==0||v==0) return u+v;// 其中一棵树为空。
    if (val[u]<val[v]) {rs[u]=merge(rs[u],v);push_up(u);return u;}// 第一棵 Treap 的根的 Value 更小。
    else {ls[v]=merge(u,ls[v]);push_up(v);return v;}// 第二棵 Treap 的根的 Value 更小。
}

通过 Split 和 Merge 可以实现平衡树的基础操作。

基础操作

插入

设插入的值为 \(k\)。

先按 \(k\) Split，然后新建一个 \(Key = k\) 的点，按顺序将第一棵树、新节点、第二棵树合并起来。

void insert(int k) {
    int u,v;
    split(root,k,u,v);
    root=merge(merge(u,new_node(k)),v);// root 用来存整个 Treap 的根的编号。
    // new_node 会新建一个 Key = k 的节点。
    return ;
}

删除

设删除的值为 \(k\)。

先按 \(k\) Split，再按 \(k+1\) Split 第二棵树，这样得到三棵树，第二棵树上所有点都满足 \(Key = k\)。我们通过合并第二棵树的左右儿子的方式删除第二棵树的根，最后再把剩下的三棵树按顺序合并起来即可。

void erase(int 	k) {
    int u,v,w;
    split(root,k,u,v);
    split(v,k+1,v,w);
    v=merge(ls[v],rs[v]);
    root=merge(merge(u,v),w);
    return ;
}

查询排名

按 \(k\) Split，答案即为第一棵树的大小 \(+ 1\)。

int order_of_key(int k) {
    int u,v;
    split(root,k,u,v);
    int ans=size[u]+1;
    root=merge(u,v);// 用完记得合并回去啊。
    return ans;
}

查询排名为 k 的数

按 BST 的写法写即可。

int find_by_order(int rk) {
    int now=root;
    while (now)
        if (rk==size[ls[now]]+1) return key[now];
        else if (rk<=size[ls[now]]) now=ls[now];
        else rk-=size[ls[now]]+1,now=rs[now];
    return -1;// 一般情况下不会执行到这一步，如果执行了要么是询问的 rk 出问题了要么是你 Treap 写萎了(^_^)。
}

查询前驱&后继

即查询排名比查询的值小 \(1\) 或大 \(1\) 的数。

int find_pre(int k) {return find_by_order(order_of_key(k)-1);}
int find_suf(int k) {return find_by_order(order_of_key(k+1));}

完整代码

struct FHQ_Treap {
	int root,cnt;
	int key[1100005],val[1100005],size[1100005];
	int ls[1100005],rs[1100005];
	int new_node(int k) {cnt++;key[cnt]=k;val[cnt]=gen();size[cnt]=1;return cnt;}
	void push_up(int now) {size[now]=size[ls[now]]+size[rs[now]]+1;return ;}
	int merge(int u,int v) {
		if (u==0||v==0) return u+v;
		if (val[u]<val[v]) {rs[u]=merge(rs[u],v);push_up(u);return u;}
		else {ls[v]=merge(u,ls[v]);push_up(v);return v;}
	}
	void split(int now,int k,int &u,int &v) {
		if (now==0) {u=v=0;return ;}
		if (key[now]<k) u=now,split(rs[now],k,rs[now],v);
		else v=now,split(ls[now],k,u,ls[now]);
		push_up(now);
		return ;
	}
	void insert(int k) {
		int u,v;
		split(root,k,u,v);
		root=merge(merge(u,new_node(k)),v);
		return ;
	}
	void erase(int 	k) {
		int u,v,w;
		split(root,k,u,v);
		split(v,k+1,v,w);
		v=merge(ls[v],rs[v]);
		root=merge(merge(u,v),w);
		return ;
	}
	int order_of_key(int k) {
		int u,v;
		split(root,k,u,v);
		int ans=size[u]+1;
		root=merge(u,v);
		return ans;
	}
	int find_by_order(int rk) {
		int now=root;
		while (now)
			if (rk==size[ls[now]]+1) return key[now];
			else if (rk<=size[ls[now]]) now=ls[now];
			else rk-=size[ls[now]]+1,now=rs[now];
		return -1;
	}
	int find_pre(int k) {return find_by_order(order_of_key(k)-1);}
	int find_suf(int k) {return find_by_order(order_of_key(k+1));}
};

文艺平衡树

题目链接：https://www.luogu.com.cn/problem/P3391

写一种数据结构，来维护一个有序数列，要求支持区间翻转操作。

参考前面实现平衡树基础操作的方式，我们考虑每次将操作区间 Split 出来，然后操作完再 Merge 回去。

然而序列显然不会有序，故 Treap 不能按值维护了。
我们考虑根据子树大小来分裂，即将 Treap 分裂成两棵树，使得第一棵树的大小恰好为某个值。

void split(int now,int sz,int &u,int &v) {
    if (now==0) {u=v=0;return ;}
    if (size[ls[now]]<sz) u=now,split(rs[now],sz-size[ls[now]]-1,rs[now],v);
    else v=now,split(ls[now],sz,u,ls[now]);
    push_up(now);
    return ;
}

对于区间翻转，我们可以使用类似于线段树的懒标记，只要每次访问到当前点时 push_down 即可。

void reverse(int l,int r) {
    int u,v,w;
    split(root,l-1,u,v);
    split(v,r-l+1,v,w);
    lzy[v]^=1;
    swap(ls[v],rs[v]);
    merge(merge(u,v),w);
    return ;
}

完整代码：

//Think twice,code once.
#include<chrono>
#include<random>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,m;
mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
struct Fido_Puppy_Treap {
	int root,cnt;
	int key[100005],val[100005],size[100005],lzy[100005];
	int ls[100005],rs[100005];
	int new_node(int k) {cnt++;key[cnt]=k;val[cnt]=gen();size[cnt]=1;return cnt;}
	void push_up(int now) {size[now]=size[ls[now]]+size[rs[now]]+1;return ;}
	void push_down(int now) {
		swap(ls[ls[now]],rs[ls[now]]);
		swap(ls[rs[now]],rs[rs[now]]);
		lzy[ls[now]]^=1;lzy[rs[now]]^=1;
		lzy[now]=0;
		return ;
	}
	int merge(int u,int v) {
		if (u==0||v==0) return u+v;
		if (lzy[u]) push_down(u);
		if (lzy[v]) push_down(v);
        // 访问到就下传。
		if (val[u]<val[v]) {rs[u]=merge(rs[u],v);push_up(u);return u;}
		else {ls[v]=merge(u,ls[v]);push_up(v);return v;}
	}
	void split(int now,int sz,int &u,int &v) {
		if (now==0) {u=v=0;return ;}
		if (lzy[now]) push_down(now);// 访问到就下传。
		if (size[ls[now]]<sz) u=now,split(rs[now],sz-size[ls[now]]-1,rs[now],v);
		else v=now,split(ls[now],sz,u,ls[now]);
		push_up(now);
		return ;
	}
	void insert(int k) {root=merge(root,new_node(k));return ;}// 这里在最后插电，故不用分裂，直接 Merge 即可。
	void reverse(int l,int r) {
		int u,v,w;
		split(root,l-1,u,v);
		split(v,r-l+1,v,w);
		lzy[v]^=1;
		swap(ls[v],rs[v]);
		merge(merge(u,v),w);
		return ;
	}
	void print(int now) {// 按顺序输出结果，直接对先序遍历即可。
		if (now==0) return ;
		if (lzy[now]) push_down(now);// 访问到就下传。
		print(ls[now]);
		printf("%d ",now);
		print(rs[now]);
		return ;
	}
}tr;

int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) tr.insert(i);
	while (m--) {
		int l,r;
		scanf("%d%d",&l,&r);
		tr.reverse(l,r);
	}
	tr.print(tr.root);
	puts("");
	return 0;
}