一些知识
二叉排序树 Binary Sort Tree
二叉排序树又称为二叉查找（搜索）树（BST）。
它或者是一颗空树，或者是具有如下性质的二叉树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。
- 它左右子树分别为二叉排序树。
BST 的特点
中序遍历递增，“拍扁了”有序。最小的在左边，最大的在最右边。
Treap
树堆。将二叉搜索树与堆结合起来，利用堆的特点来保证树的大致平衡。期望 。
这里直接放 洛谷日报 的链接和本人所写模板（不带注释 139 行与带注释 158 行比我写过的猪国杀代码行数 155 行还多，是题目 P3369 【模板】普通平衡树 的代码），这里不再赘述。
不带注释版
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=100000+10,inf=2147483647/2,NaN=0;
struct Treap
{
#define lson son[root][0]
#define rson son[root][1]
#define ms(a) memset(a,0,sizeof(a))
int son[N][2],size[N],rnk[N],val[N],num[N],cnt;
Treap()
{
ms(son);ms(num);ms(rnk);
ms(val);ms(size);
cnt=0;srand(19260817);
}
void newnode(int &root,int data)
{
root=++cnt;
val[root]=data;
size[root]=num[root]=1;
rnk[root]=rand();
}
void pushup(int root)
{
size[root]=size[lson]+size[rson]+num[root];
return;
}
void rotate(int &root,int s)
{
int ss=son[root][s^1];
son[root][s^1]=son[ss][s];
son[ss][s]=root;
pushup(root);pushup(ss);
root=ss;
}
void ins(int &root,int data)
{
if(!root)
{
newnode(root,data);
return;
}
if(val[root]==data)
{
size[root]++;
num[root]++;
return;
}
int s=(data>val[root]);
ins(son[root][s],data);
if(rnk[root]<rnk[son[root][s]])
rotate(root,s^1);
pushup(root);
}
void del(int &root,int data)
{
if(!root) return;
if(data<val[root]) del(lson,data);
else if(data>val[root]) del(rson,data);
else {
if(!lson && !rson)
{
num[root]--;size[root]--;
if(num[root]==0) root=0;
}
else if(!lson && rson)
{
rotate(root,0);
del(lson,data);
}
else if(lson && !rson)
{
rotate(root,1);
del(rson,data);
}
else
{
int s=(val[lson]>val[rson]);
rotate(root,s);
del(son[root][s],data);
}
}
pushup(root);
}
int rank(int root,int q)
{
if(!root) return NaN;
if(val[root]==q) return size[lson]+1;
if(val[root]>q) return rank(lson,q);
return size[lson]+num[root]+rank(rson,q);
}
int find(int root,int q)
{
if(!root) return NaN;
if(size[lson]>=q) return find(lson,q);
else if(size[lson]+num[root]<q)
return find(rson,q-size[lson]-num[root]);
else return val[root];
}
int pre(int root,int q)
{
if(!root) return -inf;
if(val[root]>=q) return pre(lson,q);
return max(val[root],pre(rson,q));
}
int suc(int root,int q)
{
if(!root) return inf;
if(val[root]<=q) return suc(rson,q);
return min(val[root],suc(lson,q));
}
}tree;
int root,n,opt,a;
void yzmain()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&opt,&a);
switch(opt)
{
case 1:tree.ins(root,a);break;
case 2:tree.del(root,a);break;
case 3:printf("%d\n",tree.rank(root,a));break;
case 4:printf("%d\n",tree.find(root,a));break;
case 5:printf("%d\n",tree.pre(root,a));break;
case 6:printf("%d\n",tree.suc(root,a));break;
}
}
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
带注释版
//版本 2 调试一次 调试点用 /**/ 表示
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
const int N=100000+10,inf=2147483647/2,NaN=0;
struct Treap
{
#define lson son[root][0]
#define rson son[root][1]
#define ms(a) memset(a,0,sizeof(a))
int son[N][2], //儿子寻址
size[N], //子树大小
rnk[N], //随机优先级
val[N], //值
num[N], //节点重复数字个数
cnt; //内存池
Treap()
{
ms(son);ms(num);ms(rnk);
ms(val);ms(size);
cnt=0;srand(19260817);
}
void newnode(int &root,int data)
{
root=++cnt;
val[root]=data;
size[root]=num[root]=1;
rnk[root]=rand();
}
void pushup(int root)//维护 size
{
size[root]=size[lson]+size[rson]+num[root];
return;
}
void rotate(int &root,int s)//旋转。s=1 为右旋，s=0 为左旋。
{
/*以左旋为例。
(1) 根的右儿子和根的右儿子的左儿子交换；
(2) 右儿子到达原来根的位置，形成左旋。
当前操作结点距离根结点的距离不变。*/
int ss=son[root][s^1];
son[root][s^1]=son[ss][s];//根的右儿子成为根的右儿子的左儿子。
son[ss][s]=root; //根的右儿子成为根（其左儿子是原来的根）。
pushup(root);pushup(ss); //此时原根、原根的右儿子的子树发生改变。
root=ss; //原根
}
void ins(int &root,int data)
{
if(!root)//空树或叶子节点
{
newnode(root,data);
return;
}
if(val[root]==data)
{
size[root]++;
num[root]++;
return;
}
int s=(data>val[root]); //分左右儿子。
ins(son[root][s],data); //继续查找。在查找方向上子树高必定 +0 或者 +1。
if(rnk[root]<rnk[son[root][s]])
rotate(root,s^1); //若产生新的叶子，有可能需要调整。沿来的方向反方向旋转。
pushup(root); //若不旋转，必须更新本层统计；若旋转，此时p会被更新。
}
void del(int &root,int data)
{
if(!root) return;//找不到，不删了。
if(data<val[root]) del(lson,data);
else if(data>val[root]) del(rson,data);
else {
if(!lson && !rson) //没儿子。
{
num[root]--;size[root]--;
if(num[root]==0) root=0; //没了，除名。
}
else if(!lson && rson) //没左儿子。/**/
{
//左旋，被删除点向左下沉，以保持删后平衡。
rotate(root,0);
del(lson,data);
}
else if(lson && !rson) //没右儿子/**/
{
//右旋，被删除点向右下沉，以保持删后平衡。
rotate(root,1);
del(rson,data);
}
else //两个儿子
{
//考虑删后维持大根堆。
int s=(val[lson]>val[rson]); //分左右儿子。
rotate(root,s);//把大的那个转上来，然后去另一个子树解决
del(son[root][s],data);
}
}
pushup(root);//逐层统计一下。
}
int rank(int root,int q)//查 q 在根为 root 的树中的排名
{
if(!root) return NaN;
if(val[root]==q) return size[lson]+1;
if(val[root]>q) return rank(lson,q);
return size[lson]+num[root]+rank(rson,q);//val[root]<q
}
int find(int root,int q)//查在根为 root 的子树中排名为 q 的数
{
if(!root) return NaN;
if(size[lson]>=q) return find(lson,q);
else if(size[lson]+num[root]<q)
return find(rson,q-size[lson]-num[root]);
else return val[root];
}
int pre(int root,int q)//查在根为 root 的子树中 q 的前驱
{
//precursor
if(!root) return -inf;
if(val[root]>=q) return pre(lson,q);
return max(val[root],pre(rson,q));
}
int suc(int root,int q)//查在根为 root 的子树中 q 的后继
{
//successor
if(!root) return inf;
if(val[root]<=q) return suc(rson,q);
return min(val[root],suc(lson,q));
}
}tree;
int root,n,opt,a;
void yzmain()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&opt,&a);
switch(opt)
{
case 1:tree.ins(root,a);break;
case 2:tree.del(root,a);break;
case 3:printf("%d\n",tree.rank(root,a));break;
case 4:printf("%d\n",tree.find(root,a));break;
case 5:printf("%d\n",tree.pre(root,a));break;
case 6:printf("%d\n",tree.suc(root,a));break;
}
}
return;
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
_yz::yzmain();
return 0;
}
Splay
伸展树。可以自我调整，依靠伸展操作 splay 来提升效率。功能强大，用于 LCT 的辅助树。均摊 ，常数比较大。
这里直接放出 洛谷日报 链接和本人所写模板。不带注释 156 行与带注释 175 行。
不带注释版
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const ll N=100000+10,inf=21474836471234567;
struct Splay
{
ll son[N][2],data[N],num[N],size[N],dad[N];
ll cnt;
Splay()
{
ms(son);ms(data);ms(num);
ms(size);ms(dad);cnt=0;
}
void pushup(ll pos)
{
size[pos]=num[pos]+size[son[pos][0]]+size[son[pos][1]];
return;
}
ll check(ll pos){return son[dad[pos]][1]==pos;}
void rotate(ll pos)
{
ll par=dad[pos],gpar=dad[par],way=check(pos);
ll son2=son[pos][way^1];
son[gpar][check(par)]=pos; dad[pos]=gpar;
son[par][way]=son2; dad[son2]=par;
son[pos][way^1]=par; dad[par]=pos;
pushup(par); pushup(pos);
return;
}
void splay(ll &root,ll pos,ll des)
{
while(dad[pos]!=des)
{
ll par=dad[pos],gpar=dad[par];
if(gpar!=des)
{
if(check(pos)==check(par)) rotate(par);
else rotate(pos);
}
rotate(pos);
}
if(des==0) root=pos;
}
ll _new(ll val,ll fa)
{
data[++cnt]=val;dad[cnt]=fa;
num[cnt]=1;
pushup(cnt);
return cnt;
}
void insert(ll &root,ll val)
{
ll pos=root,fa=0,way=(val>data[pos]);
if(!pos) {pos=_new(val,0);root=pos;return;}
while(pos&&data[pos]!=val)
{
fa=pos;
pos=son[pos][way];
way=(val>data[pos]);
}
if(pos) num[pos]++;
else{
pos=_new(val,fa);
if(fa) son[fa][data[fa]<val]=pos;
}
splay(root,pos,0);
}
void find(ll &root,ll x)
{
ll pos=root,way=(x>data[pos]);
if(!pos) return;
while(data[pos]!=x&&son[pos][way])
{
pos=son[pos][way];
way=(x>data[pos]);
}
splay(root,pos,0);
}
ll rank(ll &root,ll val)
{
find(root,val);
ll pos=son[root][0];
if(data[root]>=val) return size[pos]-1;
else return size[pos]+num[root]-1;
}
ll atrank(ll &root,ll x)
{
ll pos=root;
while(true)
{
ll l=son[pos][0],r=son[pos][1];
if(l&&x<=size[l]) pos=l;
else if(r&&x>size[l]+num[pos])
x-=size[l]+num[pos],pos=r;
else{
splay(root,pos,0);
return data[pos];
}
}
}
ll pre(ll &root,ll val)
{
find(root,val);
ll pos=root;
if(data[pos]<val) return pos;
pos=son[pos][0];
while(son[pos][1]) pos=son[pos][1];
return pos;
}
ll suc(ll &root,ll val)
{
find(root,val);
ll pos=root;
if(data[pos]>val) return pos;
pos=son[pos][1];
while(son[pos][0]) pos=son[pos][0];
return pos;
}
void remove(ll &root,ll val)
{
ll l=pre(root,val),r=suc(root,val);
splay(root,r,0);splay(root,l,r);
ll pos=son[l][1];
if(data[pos]!=val) return;
if(num[pos]>1)
num[pos]--,splay(root,pos,0);
else son[l][1]=0;
pushup(l);
}
}tree;
ll n,a[N],opt,x,root=0;
void yzmain()
{
scanf("%lld",&n);
tree.insert(root,inf);tree.insert(root,-inf);
for(ll i=1;i<=n;i++)
{
scanf("%lld%lld",&opt,&x);
if(opt==1) tree.insert(root,x);
else if(opt==2) tree.remove(root,x);
else if(opt==3) printf("%lld\n",tree.rank(root,x)+1);
else if(opt==4) printf("%lld\n",tree.atrank(root,x+1));
else if(opt==5) printf("%lld\n",tree.data[tree.pre(root,x)]);
else printf("%lld\n",tree.data[tree.suc(root,x)]);
}
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
带注释版
#include<bits/stdc++.h>
using namespace std;
namespace _yz
{
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const ll N=100000+10,inf=21474836471234567;
struct Splay//统一返回节点，而不是值
{//规定 pos 是节点，val 是值等于它的节点。
ll son[N][2],data[N],num[N],size[N],dad[N];
ll cnt;
Splay()//初始化。
{
ms(son);ms(data);ms(num);
ms(size);ms(dad);cnt=0;//内存池
}
void pushup(ll pos)//更新节点信息
{
size[pos]=num[pos]+size[son[pos][0]]+size[son[pos][1]];
return; //size 只需要在 pushup 时更新
}
ll check(ll pos){return son[dad[pos]][1]==pos;}//查询 pos 是左/右儿子。
//左儿子返回 0。
void rotate(ll pos)//旋转，将 pos 转上来。
{
//下面的注释基于如图的情况，另一种差不多。
/*| par pos | way，与 pos 同向，为左儿子。
| / \ / \ | son1，仍然是 pos 的左儿子。
| pos csn <--> son1 par | son2，送给 par 当左儿子。
| / \ / \ |
| son1 son2 son2 csn | */
ll par=dad[pos],gpar=dad[par],way=check(pos);
ll son2=son[pos][way^1];
son[par][way]=son2; // par 认 son2 为左儿子。
dad[son2]=par; // son2 认 par 为父亲。
son[gpar][check(par)]=pos; // gpar 认 pos 为儿子。
dad[pos]=gpar; // pos 认 gpar 为父亲。
son[pos][way^1]=par; // pos 认 par 为右儿子。
dad[par]=pos; // part 认 pos 为父亲。
pushup(par); // 至此，旋转已完成，pos 成为了 par 的父亲。
pushup(pos); // 先更新儿子，再更新父亲。
return;
}
void splay(ll &root,ll pos,ll des)//不要误认为 des 是根节点
{//将 pos 转到需要的位置，默认是根（0 节点的儿子）。
//即，转到 des 的儿子处。splay 的另一个作用是保持平衡树的平衡。
while(dad[pos]!=des)
{
ll par=dad[pos],gpar=dad[par];
if(gpar!=des)
{
if(check(pos)==check(par)) rotate(par);//“三点一线”时先转父节点。
else rotate(pos); //使得链尽可能被折叠。
}
rotate(pos);
}
if(des==0) root=pos;//如果转到根，pos 则成为新根。
}
ll _new(ll val,ll fa)
{
data[++cnt]=val;dad[cnt]=fa;
num[cnt]=1;
pushup(cnt);
return cnt;
}
void insert(ll &root,ll val)//插入 val
{
ll pos=root,fa=0,way=(val>data[pos]);//fa 是父节点。
if(!pos) {pos=_new(val,0);root=pos;return;}//特判根为空的情况
while(pos&&data[pos]!=val)
{
fa=pos;
pos=son[pos][way];
way=(val>data[pos]);
}
if(pos) num[pos]++;
else{//new 一个新节点
pos=_new(val,fa);
if(fa) son[fa][data[fa]<val]=pos;
}
splay(root,pos,0);
}
void find(ll &root,ll x)//将 val（或前驱后继）splay 到根。
{
ll pos=root,way=(x>data[pos]);//way 是决定走左/右边，下同。
if(!pos) return;
while(data[pos]!=x&&son[pos][way])
{
pos=son[pos][way];
way=(x>data[pos]);
}
splay(root,pos,0);//找到节点，splay 到根。
}
ll rank(ll &root,ll val)//查询一个数的排名（返回值）。
{
find(root,val);//find 之后，这个数是根，根据子树大小可得到排名。
ll pos=son[root][0];//平衡树中存在，好说
if(data[root]>=val) return size[pos]-1;
//如果不存在，且值比 data 小，其排名等价于 data 的排名
else return size[pos]+num[root]-1;
//反之，且值比 data 大，其排名等价于 data 的后继排名
//注意减去 -inf 的排名
//返回的是比 val 小的数的个数
}
ll atrank(ll &root,ll x)//查询第 x 大（返回数值）。
{
ll pos=root;
while(true)
{
ll l=son[pos][0],r=son[pos][1];
if(l&&x<=size[l]) pos=l;
else if(r&&x>size[l]+num[pos])
x-=size[l]+num[pos],pos=r;
else{
splay(root,pos,0);
return data[pos];
}
}
}
ll pre(ll &root,ll val)//查询 val 的前驱。
{//将该节点 find 到根后返回左子树最右边的节点。
find(root,val);
ll pos=root;
if(data[pos]<val) return pos;
pos=son[pos][0];
while(son[pos][1]) pos=son[pos][1];
return pos;
}
ll suc(ll &root,ll val)//查询 val 的后继。
{//同，返回右子树最左边的节点。
find(root,val);
ll pos=root;
if(data[pos]>val) return pos;
pos=son[pos][1];
while(son[pos][0]) pos=son[pos][0];
return pos;
}
void remove(ll &root,ll val)//删除 val。
{/* 显然，任何一个数的前驱和后继之间只有它自身。
令该点的前驱为 last，后继为 next。
那么可以考虑把前驱 splay 到根，后继 splay 到前驱的右儿子，
那么后继的左儿子就是要删除的点。*/
ll l=pre(root,val),r=suc(root,val);
splay(root,r,0);splay(root,l,r);
ll pos=son[l][1];
if(data[pos]!=val) return;
if(num[pos]>1)
num[pos]--,splay(root,pos,0);
else son[l][1]=0;
pushup(l);/*注意 pushup 的对象*/
}
}tree;
ll n,a[N],opt,x,root=0;
void yzmain()
{
scanf("%lld",&n);
tree.insert(root,inf);tree.insert(root,-inf);
for(ll i=1;i<=n;i++)
{
scanf("%lld%lld",&opt,&x);
if(opt==1) tree.insert(root,x);
else if(opt==2) tree.remove(root,x);
else if(opt==3) printf("%lld\n",tree.rank(root,x)+1);
else if(opt==4) printf("%lld\n",tree.atrank(root,x+1));
else if(opt==5) printf("%lld\n",tree.data[tree.pre(root,x)]);
else printf("%lld\n",tree.data[tree.suc(root,x)]);
}
return;
}
}
int main()
{
_yz::yzmain();
return 0;
}
FHQ Treap
对于其他的平衡树，我还不会 qwq。
本文作者：Yurchiu
本文链接：https://yz-hs.github.io/437423a190bd/
版权声明：本博客中所有原创文章除特别声明外，均允许规范转载，转载请注明出处。所有非原创文章，按照原作者要求转载。
