\(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[],t[]; 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); }

讯享网

讯享网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); }

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

#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[],t[]; 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<=;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[]; 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[],*st[]; 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<;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; }