$\text{fhq-treap}$总结

又名范浩强$\text{treap}$，是一种无旋$\text{treap}$。其原理同$\text{treap}$一样都是通过维护一个随机堆来避免退化为单链的情况，但是无需旋转$\text{rotate}$，而是通过分裂$\text{split}$完成操作。其代码极度简洁，极度舒适，反正拯救了我的平衡树。

基本操作

$\text{split}$

分裂为左右两个子树$x,y$，子树$x$内的数均$\le k$，而子树$y$内的数$ >k$。（这里是按权值分裂，还有一种按子树大小分裂的，即子树$x$大小为$k$，维护区间翻转的时候需要用）

当前节点值$\le k$时，说明当前节点及其左子树肯定都是$\le k$，当前要找的$x$子树树根就是当前节点，而$y$子树树根不确定。而且对于其右子树是否均$>k$我们并不确定，因为可能右儿子的左子树中可能还有$\le k$的，所以我们还要递归找下去。

void split(int cur, int k, int &x, int &y){

	if(cur==0){x=y=0;return;}

	if(tre[cur].val<=k){

		x=cur;

		split(tre[cur].sr, k, tre[cur].sr, y); // 递归找其右儿子

	}else{

		y=cur;

		split(tre[cur].sl, k, x, tre[cur].sl); // 递归找其左儿子

	}

	update(cur); // 更新子树大小

}

$\text{merge}$

合并两个子树$x,y$，默认子树$x$均小于子树$y$中的数

合并子树的同时利用随机权值维护一个堆（这里是小根堆）。维护堆的同时维护$\text{BST}$，让小于等于自己的数成为左儿子，大于自己的数成为右儿子。

int merge(int x, int y){

	if(!x||!y) return x|y;

	if(tre[x].rnd<tre[y].rnd){

		tre[x].sr=merge(tre[x].sr, y);

		update(x);

		return x;

	}else{

		tre[y].sl=merge(x, tre[y].sl);

		update(y);

		return y;

	}

}

$\text{new_nod}$

新建一个节点并返回其编号。

inline int new_nod(int val){

	++tot;

	tre[tot].val=val;

	tre[tot].rnd=rand();

	tre[tot].sz=1;

	return tot;

}

$\text{insert}$

插入数值$val$

inline void insert(int val){

	split(root, val, x, y);

	root=merge(merge(x, new_nod(val)), y);

}

$\text{del}$

删除数值$val$

通过两次分裂子树，定位到全为$val$子树（节点）的位置，然后直接将这个全为$val$的子树直接删除。

inline void del(int val){

	split(root, val, x, z);

	split(x, val-1, x, y);

	y=merge(tre[y].sl, tre[y].sr);

	root=merge(merge(x,y), z);

}

$\text{rank}$

获取数值$val$的排名

inline int get_rank(int val){

	split(root, val-1, x, y);

	int res=tre[x].sz+1;

	root=merge(x,y);

	return res;

}

$\text{kth}$

获得第$k$大的数值

inline int get_kth(int cur, int k){

	while(1){

		if(k<=tre[tre[cur].sl].sz) cur=tre[cur].sl;

		else if(k==tre[tre[cur].sl].sz+1) return cur;

		else k-=tre[tre[cur].sl].sz+1, cur=tre[cur].sr;

	}

}

$\text{pre}$

前驱，注意存在多个$val$数值的情况

inline int get_pre(int val){

	split(root, val-1, x, y);

	int res=get_kth(x, tre[x].sz);

	root=merge(x,y);

	return res;

}

$\text{nxt}$

后驱

inline int get_nxt(int val){

	split(root, val, x, y);

	int res=get_kth(y, 1);

	root=merge(x,y);

	return res;

}

普通平衡树

插入x数

删除x数(若有多个相同的数，因只删除一个)

查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)

查询排名为x的数

求x的前驱(前驱定义为小于x，且最大的数)

求x的后继(后继定义为大于x，且最小的数)

完整代码：

#include <cstdio>

#include <cstdlib>

#define MAXN 100010

using namespace std;

struct nod{

	int sl,sr;

	int rnd,val,sz;

} tre[MAXN];

inline void update(int x){

	tre[x].sz=tre[tre[x].sl].sz+tre[tre[x].sr].sz+1;

}

int merge(int x, int y){

	if(!x||!y) return x|y;

	if(tre[x].rnd<tre[y].rnd){

		tre[x].sr=merge(tre[x].sr, y);

		update(x);

		return x;

	}else{

		tre[y].sl=merge(x, tre[y].sl);

		update(y);

		return y;

	}

}

void split(int cur, int k, int &x, int &y){

	if(cur==0){

		x=y=0;

		return;

	}

	if(tre[cur].val<=k){

		x=cur;

		split(tre[cur].sr, k, tre[cur].sr, y);

	}else{

		y=cur;

		split(tre[cur].sl, k, x, tre[cur].sl);

	}

	update(cur);

}

int tot,root,x,y,z;

inline int new_nod(int val){

	++tot;

	tre[tot].val=val;

	tre[tot].rnd=rand();

	tre[tot].sz=1;

	return tot;

}

inline void insert(int val){

	split(root, val, x, y);

	root=merge(merge(x, new_nod(val)), y);

}

inline void del(int val){

	split(root, val, x, z);

	split(x, val-1, x, y);

	y=merge(tre[y].sl, tre[y].sr);

	root=merge(merge(x,y), z);

}

inline int get_rank(int val){

	split(root, val-1, x, y);

	int res=tre[x].sz+1;

	root=merge(x,y);

	return res;

}

inline int get_kth(int cur, int k){

	while(1){

		if(k<=tre[tre[cur].sl].sz) cur=tre[cur].sl;

		else if(k==tre[tre[cur].sl].sz+1) return cur;

		else k-=tre[tre[cur].sl].sz+1, cur=tre[cur].sr;

	}

}

inline int get_pre(int val){

	split(root, val-1, x, y);

	int res=get_kth(x, tre[x].sz);

	root=merge(x,y);

	return res;

}

inline int get_nxt(int val){

	split(root, val, x, y);

	int res=get_kth(y, 1);

	root=merge(x,y);

	return res;

}

int t;

int main()

{

	srand((unsigned)19270817);

	scanf("%d", &t);

	while(t--){

		int opt,a;

		scanf("%d %d", &opt, &a);

		if(opt==1) insert(a);

		else if(opt==2) del(a);

		else if(opt==3) printf("%d\n", get_rank(a));

		else if(opt==4) printf("%d\n", tre[get_kth(root, a)].val);

		else if(opt==5) printf("%d\n", tre[get_pre(a)].val);

		else printf("%d\n", tre[get_nxt(a)].val);

	}

	return 0;

}

文艺平衡树

支持区间翻转，多次区间翻转，最后询问最终序列

这里我们就按树大小分裂子树，每次翻转区间$[l,r]$时，通过两次分裂找出包含区间$[l,r]$的树，然后用懒标记标记一下（$change$表示是否旋转当前树所代表的区间）。每次操作或查询前下放标记即可。

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#define MAXN 100010

using namespace std;

struct nod{

    int l,r,val,rnd,sz;

    bool change;

} tre[MAXN];

int rot,tot;

inline void push_down(int x){

    swap(tre[x].l, tre[x].r);

    if(tre[x].l) tre[tre[x].l].change=!tre[tre[x].l].change;

    if(tre[x].r) tre[tre[x].r].change=!tre[tre[x].r].change;

    tre[x].change=0;

}

inline void update(int x){

    tre[x].sz=tre[tre[x].l].sz+tre[tre[x].r].sz+1;

}

inline int new_nod(int val){

	++tot;

	tre[tot].val=val;

	tre[tot].rnd=rand();

	tre[tot].sz=1;

	return tot;

}

int merge(int x, int y){

    if(x==0||y==0) return x|y;

    if(tre[x].rnd<tre[y].rnd){

        if(tre[x].change) push_down(x);

        tre[x].r=merge(tre[x].r, y);

        update(x);

        return x;

    }else{

        if(tre[y].change) push_down(y);

        tre[y].l=merge(x, tre[y].l);

        update(y);

        return y;

    }

}

void split(int cur, int k, int &x, int &y){

    if(!cur){x=y=0;return;}

    if(tre[cur].change) push_down(cur);

    if(tre[tre[cur].l].sz<k){

        x=cur;

        split(tre[cur].r, k-tre[tre[cur].l].sz-1, tre[cur].r, y);

    }else{

        y=cur;

        split(tre[cur].l, k, x, tre[cur].l);

    }

    update(cur);

}

void change(int l, int r){

    int x,y,z;

    split(rot,l-1,x,y);

    split(y,r-l+1,y,z);

    tre[y].change=!tre[y].change;

    rot=merge(merge(x,y),z);

}

void dfs(int x){

    if(!x) return;

    if(tre[x].change) push_down(x);

    dfs(tre[x].l);

    printf("%d ", tre[x].val);

    dfs(tre[x].r);

}

int n,m;

int main()

{

    srand((unsigned)19270817);

    scanf("%d %d", &n, &m);

    for(int i=1;i<=n;++i) rot=merge(rot, new_nod(i));

    while(m--){

        int l,r;

        scanf("%d %d", &l, &r);

        change(l, r);

    }

    dfs(rot);

    return 0;

}

巴特西

$\text{fhq-treap}$总结

\(\text{fhq-treap}\)总结

基本操作

\(\text{split}\)

\(\text{merge}\)

\(\text{new_nod}\)

\(\text{insert}\)

\(\text{del}\)

\(\text{rank}\)

\(\text{kth}\)

\(\text{pre}\)

\(\text{nxt}\)

普通平衡树

文艺平衡树

最新文章

热门文章