前言

原文写于 XJ 集训day2 2020.1.19.

现在想想那时候连模板都还没写，只是刚刚理解就在那里瞎yy……之前果然还是太幼稚了。

今天刷训练指南发现全是 Treap 和 Splay ，不想写所以就来重写这个坑。

普通平衡树模板

基本思想：通过对平衡树进行分割（split）和合并（merge）完成维护平衡。

基本操作：插入，删除，查询排名，查询数值，求前驱，求后继

高级操作：可持久化，区间操作

显然我们是要维护一组数据。对于这组数据，每个点的值就是这棵平衡树的点权。根据基本性质，从点权角度看这棵树，满足二叉搜索树(BST)

然后 FHQ-Treap 还有一个附加值来维护平衡，这个值通常是随机出来的，且整棵树的附加值满足堆的性质。

有一说一，FHQ这样函数封装的是真的舒服……那我就直接讲函数好了。

模板题

1. 基本操作

struct FHQTreap

{

    int l,r,val,rnd,siz;

}tr[N];

int cnt=0,rt=0,tx,ty,tz;

void update( int x )            //用左右子树的大小更新父节点子树大小

{

    tr[x].siz=1+tr[tr[x].l].siz+tr[tr[x].r].siz;

}

int new_node( int val )            //新建一个节点（或者说 Treap ）

{

    tr[++cnt].siz=1; tr[cnt].val=val; tr[cnt].rnd=rand(); return cnt;

}

1. Split

这个函数用途是按照某个方式分割一棵 Treap.

首先是按照权值的写法：

如果当前点的权值不大于 k ，根据二叉搜索树的性质，答案节点肯定在右子树里面。那么就将当前节点给分裂之后的“左树”\(x\) ，递归分割右子树。

如果当前节点权值大于 k，那么就同理赋值并递归分割左子树。

最后不要忘记 update。

void split( int now,int k,int &x,int &y )

{   //split a Treap by val

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

    if ( tr[now].val<=k ) x=now,split( tr[now].r,k,tr[now].r,y );

    //now比k小，左子树+根节点→x，递归分割右子树

    else y=now,split( tr[now].l,k,x,tr[now].l );

    update( now );

}

然后是按照排名的写法：

如果 k 不大于左子树大小，那么就是在左子树或者根节点，递归分割左子树；否则递归分割右子树，不过排名 k 要减去左子树大小和根节点。

void split( int now,int k,int &x,int &y )

{

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

    if ( k<=tr[tr[now].l].siz ) y=now,split( tr[now].l,k,x,tr[now].l );

    else x=now,split( tr[now].r,k-tr[tr[now].l].size-1,tr[now].r,y );

    update( now );

}

2. Merge

顾名思义，就是合并两棵 Treap.

首先要保证 (x,y) 的顺序满足二叉搜索树的性质，所以merge的时候要注意顺序。

其次还要考虑附加值的堆性质。如果 \(x\) 的 rnd 比 \(y\) 大，那么说明在 “堆” 里面 \(x\) 应该是根节点，所以就递归，把 \(x\) 的右子树和 \(y\) 合并并更新 \(x\) .反之亦然。

int merge( int x,int y )

{

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

    if ( tr[x].rnd<tr[y].rnd )

    {    //make y -> x's right child

        tr[x].r=merge( tr[x].r,y ); update( x ); return x;

    }

    else

    {   //make x -> y's left child

        tr[y].l=merge( x,tr[y].l ); update( y ); return y;

    }

}

3. Kth

相当于一个查询操作，询问第 k 个权值。

如果当前的 k 不大于左子树大小，那么就递归左子树；

如果正好等于左子树+1（也就是比它小的数的个数+1，就是它本身），那么就算找到了，返回；

否则和排名 split 类似，减去左子树大小和根节点，递归右子树。

这里采用 while 替代递归。

int get_kth( int now,int k )

{

    while ( 1 )

    {

        if ( k<=tr[tr[now].l].siz ) now=tr[now].l;

        //k<=tr[l].size,the node must be in the left subtree

        else if ( k==tr[tr[now].l].siz+1 ) return now;

        //the kth node is exactly tree 'now'

        else k-=tr[tr[now].l].siz+1,now=tr[now].r;

        //k-=left subtree's size and 1 for the root,then search in the right subtree

    }

}

4. 基本查询

插入

按照权值分割，然后合并左树和新节点，再和右树合并。

        if ( opt==1 )           //insert

        {

            split( rt,x,tx,ty ); rt=merge( merge(tx,new_node(x)),ty );

        }

删除

先按照权值 \(x\) 分割，然后再把小于 \(x\) 的部分分割出来，对于剩下的就是等于 \(x\) 的部分。这部分由于是删除一个节点（但是实际会有多个重复的点），所以直接忽略根节点合并左右子树即可。最后再和之前分出来的两部分合并，注意顺序。

（其实还有一种方法是同时在一个节点里面记录出现次数，删除减一即可）

（重复节点对 FHQ 是没有大问题的……但是对于伸展树嘛……初始节点一定要放啊……）

        if ( opt==2 )               //delete

        {

            split( rt,x,tx,tz ); split( tx,x-1,tx,ty );

            ty=merge( tr[ty].l,tr[ty].r ); rt=merge( merge(tx,ty),tz );

        }

根据值求排名

分割出左子树，然后左子树 siz +1 即可（原因自己读题）

        if ( opt==3 )               //get rank by val

        {

            split( rt,x-1,tx,ty ); printf( "%d\n",tr[tx].siz+1 ); rt=merge( tx,ty );

        }

Kth

        if ( opt==4 ) printf( "%d\n",tr[get_kth(rt,x)].val );               //get val by rank

求前驱

        if ( opt==5 )           //get pre node

        {

            split( rt,x-1,tx,ty );

            printf( "%d\n",tr[get_kth(tx,tr[tx].siz)].val );

            rt=merge( tx,ty );

        }

求后继

        if ( opt==6 )           //get suf node

        {

            split( rt,x,tx,ty );

            printf( "%d\n",tr[get_kth(ty,1)].val );

            rt=merge( tx,ty );

        }

文艺平衡树

模板题

题目要求是翻转区间，意思就是要支持区间操作（

代码可以直接在普通平衡树上面修改得到，这里只放一些不同的部分。

0. 【Important】Reverse

针对这道题的区间翻转操作，就是对 tag 进行修改。

主要这里涉及到了如何把一个区间抠出来进行操作。

思想很简单，就是把右端点 r 右边的分开，左端点之前的分开，然后对中间这段进行操作即可。

void reverse( int l,int r )

{

    int t1,t2,t3,t4;

    split( rt,r,t1,t2 ); split( t1,l-1,t3,t4 );

    tr[t4].mark^=1; rt=merge( merge( t3,t4 ),t2 );

}

1. 基本操作

就是给原来的结构体加了翻转的 tag。

struct FHQTreap

{

    int l,r,val,rnd,siz,mark;

}tr[N];

2. Pushdown

类似线段树的标记下传。

void pushdown( int x )

{

    if ( x && tr[x].mark )

    {

        tr[x].mark=0; swap( tr[x].l,tr[x].r );

        if ( tr[x].l ) tr[tr[x].l].mark^=1;

        if ( tr[x].r ) tr[tr[x].r].mark^=1;

    }

}

3. Merge

合并操作中增加pushdown.

int merge( int x,int y )

{

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

    pushdown( x ); pushdown( y );

    if ( tr[x].rnd<tr[y].rnd )

    {    //make y -> x's right child

        tr[x].r=merge( tr[x].r,y ); update( x ); return x;

    }

    else

    {   //make x -> y's left child

        tr[y].l=merge( x,tr[y].l ); update( y ); return y;

    }

}

4. Split

由于是要翻转区间，所以一定要按照子树大小分割了。

记得下传。

void split( int now,int k,int &x,int &y )

{

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

    pushdown( now );

    if ( k<=tr[tr[now].l].siz ) y=now,split( tr[now].l,k,x,tr[now].l );

    else x=now,split( tr[now].r,k-tr[tr[now].l].siz-1,tr[now].r,y );

    update( now );

}

5. Build

新增的建树函数。总体结构类似线段树建树。

int build( int l,int r )

{

    if ( l>r ) return 0;

    int mid=(l+r)>>1,val=mid;

    int now=new_node( val );

    tr[now].l=build( l,mid-1 ); tr[now].r=build( mid+1,r );

    update( now );

    return now;

}

6. 输出

这个是针对这道题的……就是中序遍历输出。

void dfs( int x )

{

    if ( !x ) return;

    pushdown( x );

    dfs( tr[x].l );

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

    dfs( tr[x].r );

}

巴特西

FHQ简要笔记

前言

普通平衡树模板

1. 基本操作

1. Split

2. Merge

3. Kth

4. 基本查询

插入

删除

根据值求排名

Kth

求前驱

求后继

文艺平衡树

0. 【Important】Reverse

1. 基本操作

2. Pushdown

3. Merge

4. Split

5. Build

6. 输出

最新文章

热门文章