Early's Blog

Hello, World!

0%

可持久化平衡树学习笔记

发表于 分类于
本文字数： 3.2k

简介

FHQ Treap，又叫无旋 Treap，是一种平衡树，还可以支持可持久化，代码也通俗易懂。

例题

实现

每个节点需保存它所维护的值 valval，它的子树大小 sizsiz，父节点 fafa 以及它的左儿子 lsonlson 和右儿子 rsonrson。

1
2
3
4
5
struct tree {
    int val,pri,siz;
    tree *lson,*rson;
};
tree nul{0,0,0,&nul,&nul},*root[N+1];

建立新节点

像 Treap 一样赋予随机值。

1
2
3
4
5
6
inline tree *new_tree(int val)
{
    tree *x=new tree;
    *x=tree{val,rand(),1,&nul,&nul};
    return x;
}

复制节点

1
2
3
4
5
6
inline tree *copy(tree *ori)
{
    tree *x=new tree;
    *x=*ori;
    return x;
}

更新节点 siz

1
2
3
4
5
inline void push_up(tree *x)
{
    x->siz=x->lson->siz+x->rson->siz+1;
    return;
}

合并

合并 xx 和 yy。（保证 xx 的权值 ≤y\leq y 的权值）

如果两个节点中有空节点，则返回非空节点。

根据 Treap 的堆性质，选择随机值较大的点（假设是 xx），合并它的右儿子（如果是 yy 则为它的左儿子）与 yy。

由于需要可持久化，需要重建 xx 节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
tree *merge(tree *x,tree *y)
{
    if((x==&nul)||(y==&nul)) {
        return x==&nul?y:x;
    }
    if(x->pri<=y->pri) {
        y=copy(y);
        y->lson=merge(x,y->lson);
        push_up(y);
        return y;
    } else {
        x=copy(x);
        x->rson=merge(x->rson,y);
        push_up(x);
        return x;
    }
}

分裂

将 xx 分成权值 ≤val\leq val 的树和权值 >val>val 的树。

如果 xx 的权值 ≤val\leq val，则把 xx 的右儿子分裂，否则分裂左儿子。

注意可持久化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void split(tree *x,int val,tree *&l,tree *&r)
{
    if(x==&nul) {
        l=r=&nul;
        return;
    }
    if(x->val<=val) {
        l=copy(x);
        split(l->rson,val,l->rson,r);
        push_up(l);
    } else {
        r=copy(x);
        split(r->lson,val,l,r->lson);
        push_up(r);
    }
    return;
}

插入值

将 rootroot 分裂成分成权值 ≤val\leq val 的树 ll 与权值 >val>val 的树 rr。

新建一个值为 valval 的节点（设为 xx）。

依次合并 l,x,rl,x,r 即可。

1
2
3
4
5
6
7
8
void insert(tree *&root,int val)
{
    tree *l,*r;
    split(root,val,l,r);
    tree *x=new_tree(val);
    root=merge(l,merge(x,r));
    return;
}

删除值

将 rootroot 分裂成分成权值 <val<val 的树 ll、权值 =val=val 的树 midmid 与权值 >val>val 的树 rr。

依次合并 l,lsonmid,rsonmid,rl,lson_{mid},rson_{mid},r 即可。

1
2
3
4
5
6
7
8
9
10
11
void del(tree *&root,int val)
{
    tree *l,*l_mid,*mid,*r;
    split(root,val,l_mid,r);
    split(l_mid,val-1,l,mid);
    root=merge(l,merge(merge(mid->lson,mid->rson),r));
    if(mid!=&nul) {
        delete mid;
    }
    return;
}

查询排名为 rnk 的数

  • 如果 rnkrnk 小于等于当前节点左子树的 sizsiz，则递归左子树；

  • 否则将 rnkrnk 减去左子树的 siz+1siz+1，如果 rnk≤0rnk\leq0，则返回当前节点的权值，否则递归右子树。

1
2
3
4
5
6
7
8
int rnk2val(tree *x,int rnk)
{
    if(rnk<=x->lson->siz) {
        return rnk2val(x->lson,rnk);
    }
    rnk-=x->lson->siz+1;
    return rnk?rnk2val(x->rson,rnk):x->val;
}

查询 val 的排名

把 rootroot 分裂为权值 <val<val 的树 ll 与权值 ≥val\geq val 的树 rr。

统计 sizl+1siz_l+1 即为答案。

1
2
3
4
5
6
7
8
int val2rnk(tree *&root,int val)
{
    tree *l,*mid_r;
    split(root,val-1,l,mid_r);
    int ret=l->siz+1;
    root=merge(l,mid_r);
    return ret;
}

查询 val 的前驱

把 rootroot 分裂为权值 <val<val 的树 ll 与权值 ≥val\geq val 的树 rr。

查询 ll 中排名为 sizlsiz_l 的数。

1
2
3
4
5
6
7
8
9
10
11
int val2pre(tree *&root,int val)
{
    tree *l,*r;
    split(root,val-1,l,r);
    if(l==&nul) {
        return -inf;
    }
    int ret=rnk2val(l,l->siz);
    root=merge(l,r);
    return ret;
}

查询 val 的后继

把 rootroot 分裂为权值 ≤val\leq val 的树 ll 与权值 >val>val 的树 rr。

查询 rr 中最小的（排名为 11）的数。

1
2
3
4
5
6
7
8
9
10
11
int val2suc(tree *&root,int val)
{
    tree *l,*r;
    split(root,val,l,r);
    if(r==&nul) {
        return inf;
    }
    int ret=rnk2val(r,1);
    root=merge(l,r);
    return ret;
}