Leafy tree 详解

\(Leafy\) \(tree\)是什么？
一种依靠旋转维持重量平衡的平衡树。

\(Leafy\) \(tree\) 特点：

1. 所有的信息维护在叶子节点上；
2. 类似Kruskal重构树的结构，每个非叶子节点一定有两个孩子，且非叶子节点统计两个孩子的信息（类似线段树上传信息），所以维护\(n\)个信息的\(leafy\) \(tree\) 有 \(n \times 2 - 1\)个节点。
3. 可以完成区间操作（翻转）、可持久化等。

\(Leafy\) \(tree\) 的旋转操作：
类似于替罪羊树，在一个子树中左右孩子重量极度不平衡时进行调节，但不同的是不需要暴力重构，仅需一次旋转即可。
C++代码：

#define new_Node(a,b,c,d) (&(*st[cnt++]=Node(a,b,c,d)))
#define merge(a,b) new_Node(a->size+b->size,b->val,a,b) 
#define ratio 4

struct Node {
	int size,val;
	Node *lf,*rf;
	Node(int a,int b,Node *l,Node *r):size(a),val(b),lf(l),rf(r) {}
	Node() {}
}; Node *root,*null,*st[200010],t[200010];

inline void rotate(Node *u) {
	if(u->lf->size>u->rf->size*ratio)
		u->rf=merge(u->lf->rf,u->rf),st[--cnt]=u->lf,u->lf=u->lf->lf;
	if(u->rf->size>u->lf->size*ratio)
		u->lf=merge(u->lf,u->rf->lf),st[--cnt]=u->rf,u->rf=u->rf->rf;
}

\(Leafy\) \(tree\)的插入操作：
类似二叉树插入的过程，结束后在路径上，进行旋转调节即可。
C++代码：

inline void insert(Node *u,int x) {
	if(u->size==1)
		u->lf=new_Node(1,Min(u->val,x),null,null),
		u->rf=new_Node(1,Max(u->val,x),null,null);
	else	insert(x>u->lf->val?	u->rf:u->lf,x);
	update(u),rotate(u);
}

\(Leafy\) \(tree\) 的删除操作：
根据二叉搜索树的性质，找到要删除的数所在的父亲节点，再暴力枚举在左孩子还是右孩子，然后将剩下的一个节点合并到当前节点。
C++代码：

inline void erase(Node *u,int x) {
	if(u->lf->size==1&&u->lf->val==x)
		st[--cnt]=u->lf,st[--cnt]=u->rf,*u=*u->rf;
	else if(u->rf->size==1&&u->rf->val==x)
		st[--cnt]=u->lf,st[--cnt]=u->rf,*u=*u->lf;
	else	erase(x>u->lf->val?	u->rf:u->lf,x);
	update(u),rotate(u);
}

查找第k大：
C++代码：

inline int find(Node *u,int x) {
	if(u->size==1)	return u->val;
	return u->lf->size<x?	find(u->rf,x-u->lf->size):find(u->lf,x);
}

查找元素排名：
C++代码：

inline int Rank(Node *u,int x) {
	if(u->size==1)	return 1;
	return u->lf->val<x?	u->lf->size+Rank(u->rf,x):Rank(u->lf,x);
}

查找前驱：
C++代码：

inline int pre(int x) { return find(root,Rank(root,x)-1); }

查找后继：
C++代码：

inline int nxt(int x) { return find(root,Rank(root,x+1)); }

枚举集合中的元素：
C++代码：

inline void debug(Node *u) {
	if(u->lf!=null)	debug(u->lf);
	if(u->size==1)	printf(" %d",u->val);
	if(u->rf!=null)	debug(u->rf);
}

【模板】普通平衡树 代码：

#include<bits/stdc++.h>
#define update(u) if(u->lf->size)\
					u->size=u->lf->size+u->rf->size,u->val=u->rf->val
#define new_Node(a,b,c,d) (&(*st[cnt++]=Node(a,b,c,d)))
#define merge(a,b) new_Node(a->size+b->size,b->val,a,b)
#define ratio 4
using namespace std;

inline int Min(const int x,const int y) { return x<y?	x:y; }
inline int Max(const int x,const int y) { return x>y?	x:y; }
int n,cnt;
struct Node {
	int size,val;
	Node *lf,*rf;
	Node(int a,int b,Node *l,Node *r):size(a),val(b),lf(l),rf(r) {}
	Node() {}
};
Node *root,*null,*st[200010],t[200010];
inline void rotate(Node *u) {
	if(u->lf->size>u->rf->size*ratio)
		u->rf=merge(u->lf->rf,u->rf),st[--cnt]=u->lf,u->lf=u->lf->lf;
	if(u->rf->size>u->lf->size*ratio)
		u->lf=merge(u->lf,u->rf->lf),st[--cnt]=u->rf,u->rf=u->rf->rf;
}
inline void insert(Node *u,int x) {
	if(u->size==1)
		u->lf=new_Node(1,Min(u->val,x),null,null),
		u->rf=new_Node(1,Max(u->val,x),null,null);
	else	insert(x>u->lf->val?	u->rf:u->lf,x);
	update(u),rotate(u);
}
inline void erase(Node *u,int x) {
	if(u->lf->size==1&&u->lf->val==x)
		st[--cnt]=u->lf,st[--cnt]=u->rf,*u=*u->rf;
	else if(u->rf->size==1&&u->rf->val==x)
		st[--cnt]=u->lf,st[--cnt]=u->rf,*u=*u->lf;
	else	erase(x>u->lf->val?	u->rf:u->lf,x);
	update(u),rotate(u);
}
inline int find(Node *u,int x) {
	if(u->size==1)	return u->val;
	return u->lf->size<x?	find(u->rf,x-u->lf->size):find(u->lf,x);
}
inline int Rank(Node *u,int x) {
	if(u->size==1)	return 1;
	return u->lf->val<x?	u->lf->size+Rank(u->rf,x):Rank(u->lf,x);
}
inline int pre(int x) { return find(root,Rank(root,x)-1); }
inline int nxt(int x) { return find(root,Rank(root,x+1)); }
inline void debug(Node *u) {
	if(u->lf!=null)	debug(u->lf);
	if(u->size==1)	printf(" %d",u->val);
	if(u->rf!=null)	debug(u->rf);
}
int main() {
	scanf("%d",&n);cnt=0;
	null=new Node(0,0,0,0);
	root=new Node(1,INT_MAX,null,null);
	for(register int i=0;i<=200000;i++)	st[i]=&t[i];
	for(register int i=1;i<=n;i++) {
		register int t,a;
		scanf("%d%d",&t,&a);
		if(t==1)	insert(root,a);
		else if(t==2)	erase(root,a);
		else if(t==3)	printf("%d\n",Rank(root,a));
		else if(t==4)	printf("%d\n",find(root,a));
		else if(t==5)	printf("%d\n",pre(a));
		else if(t==6)	printf("%d\n",nxt(a));
//		debug(root);printf("\n");
	}
	return 0;
}

Leafy tree 维护区间：
类似Splay，通过旋转夹取区间，时间复杂度期望\(O(\log n)\)（不是很优秀）
【模板】文艺平衡树
C++代码：

#include<bits/stdc++.h>
#define Newnode(L,R,S,tag,V) (&(*st[tot++]=P(L,R,S,tag,V)))
#define merge(a,b) Newnode(a,b,a->sz+b->sz,0,b->val)
#define ratio 4
using namespace std;
int n,m,tot=0,a[100010];
struct P {
	int sz,lz,val; P *lf,*rf;
	P() {}
	P(P *L,P *R,int S,int tag,int V):
		lf(L),rf(R),sz(S),lz(tag),val(V) {}
};P t[200010],*st[200010];
P *root,*null;

inline void pushup(P *u) {
	if(u->lf->sz)	u->sz=u->lf->sz+u->rf->sz,u->val=u->rf->val;
}
inline void pushdown(P *u) {
	if(u->lz)
		swap(u->lf,u->rf),u->lf->lz^=1,u->rf->lz^=1,u->lz=0;
}
void Split(P *u,int s) {
	pushdown(u);
	if(s>u->lf->sz)
		Split(u->rf,s-u->lf->sz),u->lf=merge(u->lf,u->rf->lf),
		st[--tot]=u->rf,u->rf=u->rf->rf;
	else if(s<u->lf->sz)
		Split(u->lf,s),u->rf=merge(u->lf->rf,u->rf),
		st[--tot]=u->lf,u->lf=u->lf->lf;
}
P *build(int l,int r) {
	if(l>=r)	return Newnode(null,null,1,0,a[l]);
	int mid=(l+r)>>1;
	return Newnode(build(l,mid),build(mid+1,r),r-l+1,0,r);
}
inline void dfs(P *u) {
	pushdown(u);
	if(u->lf!=null)	dfs(u->lf);
	if(u->sz==1&&u->val)	printf("%d ",u->val);
	if(u->rf!=null)	dfs(u->rf);
}
int main() {
	null=new P(0,0,0,0,0);
	for(int i=0;i<200010;i++)	st[i]=&t[i];
	scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)	a[i]=i;
	root=build(0,n+1);
	while(m--) {
		int l,r;scanf("%d%d",&l,&r);
		Split(root,r+1),Split(root->lf,l);
		root->lf->rf->lz^=1;
	}
	dfs(root);
	return 0;
}