远航休息栈
首页 > 笔记 > fhq treap总结

fhq treap总结

来一发数据结构

首先Orz fhq %%%%%

何为Treap

Treap是一种二叉平衡树。Treap=BST+Heap

Treap比较好玩的一点是，它整体是拥有二叉搜索树的性质，但是它的每一个节点都会有一个附加权值，它的附加权值是符合堆的性质。

这样我们可以明显看出，这棵树的形态(平衡与否)是由这个附加权值决定的。

那我们该如何取这个权值呢？随机！！

是的，我们每次都随机一个权值作为它的附加权值，那么它就大概是平衡的。

但是一般的平衡树都会有很恼人的旋转，又不好写，又不好调。

这里就郑重推出：fhq treap!

只需要两个基础操作，就可以达到splay的所有功能

1： ￥split￥

它的主要思想就是把一个Treap分成两个。

split操作有两种类型，一种是按照权值分配，一种是按前k个分配。

第一种就是把所有小于k的权值的节点分到一棵树中，第二种是把前k个分到一个树里。

权值版：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void split(int now,int k,int &x,int &y)
{
    if (!now) x=y=0;
    else
    {
        if (val[now]<=k)
            x=now,split(ch[now][1],k,ch[now][1],y);
        else
            y=now,split(ch[now][0],k,x,ch[now][0]);
        update(now);
    }
}
 

对于我们遍历到每一个点，假如它的权值小于k，那么它的所有左子树，都要分到左边的树里，然后遍历它的右儿子。假如大于k，把它的所有右子树分到右边的树里，遍历左儿子。

因为它的最多操作次数就是一直分到底，效率就是$O(\log n)$。

对于前k个版的，就是像找第k大的感觉。每次减掉siz

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void split(int now,int k,int &x,int &y)
{
    if (!now) x=y=0;
    else
    {
        if (k<=siz[ch[now][0]])
            y=now,split(ch[now][0],k,x,ch[now][0]);
        else
            x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
        update(now);
    }
}
 

2： $merge$

这个就是把两个Treap合成一个，保证第一个的权值小于第二个。


！！！此GIF有问题，详见评论区！！！

因为第一个Treap的权值都比较小，我们比较一下它的tar(附加权值)，假如第一个的tar小，我们就可以直接保留它的所有左子树，接着把第一个Treap变成它的右儿子。反之，我们可以保留第二棵的所有右子树，指针指向左儿子。

你可以把这个过程形象的理解为在第一个Treap的左子树上插入第二个树，也可以理解为在第二个树的左子树上插入第一棵树。因为第一棵树都满足小于第二个树，所以就变成了比较tar来确定树的形态。

也就是说，我们其实是遍历了第一个trep的根->最大节点，第二个Treap的根->最小节点，也就是$O(\log n)$

代码：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (pri[x]<pri[y])
    {
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x;
    }
    else
    {
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y;
    }
}
 

下面我们就可以通过这两个基本的东西实现各种各样的操作了。

3：$insert$

插入一个权值为v的点，把树按照v的权值split成两个，再按照顺序merge回去。

C++
1
2
3
split(root,v,x,y);
root=merge(merge(x,new_node(v)),y);
 

4： $del$

删除权值为v的点，把树按照v分成两个a,b,再把a按照v-1分成c,d。把c的两个子儿子merge起来，再merge(merge(c,d),b)

C++
1
2
3
4
5
split(root,v,x,z);
split(x,v-1,x,y);
y=merge(ch[y][0],ch[y][1]);
root=merge(merge(x,y),z);
 

5： $precursor$

找前驱的话把root按v-1 split成x,y，在x里面找最大值

6： $successor$

找后继的话把root按v split成x,y，在y里找最小值

7： $rank$

把root按v-1 split成x,y，排名是x的siz

代码：普通平衡树

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <cstdio>
#include <cstdlib>
#include <ctime>
#define N 500005
using namespace std;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ch[N][2],val[N],pri[N],siz[N],sz;
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
int new_node(int v)
{
    siz[++sz]=1;
    val[sz]=v;
    pri[sz]=rand();
    return sz;
}
int merge(int x,int y)
{
    if (!x || !y) return x+y;
    if (pri[x]<pri[y])
    {
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x;
    }
    else
    {
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y;
    }
}
void split(int now,int k,int &x,int &y)
{
    if (!now) x=y=0;
    else
    {
        if (val[now]<=k)
            x=now,split(ch[now][1],k,ch[now][1],y);
        else
            y=now,split(ch[now][0],k,x,ch[now][0]);
        update(now);
    }
}
int kth(int now,int k)
{
    while(1)
    {
        if (k<=siz[ch[now][0]])
            now=ch[now][0];
        else
        if (k==siz[ch[now][0]]+1)
            return now;
        else
            k-=siz[ch[now][0]]+1,now=ch[now][1];
    }
}
main()
{
    srand((unsigned)time(NULL));
    int T,com,x,y,z,a,b,root=0;
    scanf("%d",&T);
    while(T--)
    {
        com=read(),a=read();
        if (com==1)
        {
            split(root,a,x,y);
            root=merge(merge(x,new_node(a)),y);
        }
        else
        if (com==2)
        {
            split(root,a,x,z);
            split(x,a-1,x,y);
            y=merge(ch[y][0],ch[y][1]);
            root=merge(merge(x,y),z);
        }
        else
        if (com==3)
        {
            split(root,a-1,x,y);
            printf("%d\n",siz[x]+1);
            root=merge(x,y);
        }
        else
        if (com==4)
            printf("%d\n",val[kth(root,a)]);
        else
        if (com==5)
        {
            split(root,a-1,x,y);
            printf("%d\n",val[kth(x,siz[x])]);
            root=merge(x,y);
        }
        else
        {
            split(root,a,x,y);
            printf("%d\n",val[kth(y,1)]);
            root=merge(x,y);
        }
    }
}
 

代码非常短小精悍

那我们该如何操作区间呢？

我们先把root的前r个split出来，再在前面的子树中split前l-1个，然后我们就得到了操作区间

模版：文艺平衡树

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#define N 500005
using namespace std;
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int ch[N][2],val[N],pri[N],siz[N],mark[N],sz,root,n,m;
void update(int x){siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];}
void pushdown(int x)
{
    if (x && mark[x])
    {
        mark[x]=0;
        swap(ch[x][0],ch[x][1]);
        if (ch[x][0]) mark[ch[x][0]]^=1;
        if (ch[x][1]) mark[ch[x][1]]^=1;
    }
}
int new_node(int v)
{
    siz[++sz]=1;
    val[sz]=v;
    pri[sz]=rand();
    return sz;
}
int merge(int x,int y)
{
    if (!x || !y) return x+y;
    pushdown(x);pushdown(y);
    if (pri[x]<pri[y])
    {
        ch[x][1]=merge(ch[x][1],y);
        update(x);
        return x;
    }
    else
    {
        ch[y][0]=merge(x,ch[y][0]);
        update(y);
        return y;
    }
}
void split(int now,int k,int &x,int &y)
{
    if (!now) x=y=0;
    else
    {
        pushdown(now);
        if (k<=siz[ch[now][0]])
            y=now,split(ch[now][0],k,x,ch[now][0]);
        else
            x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
        update(now);
    }
}
int build(int l,int r)
{
    if (l>r) return 0;
    int mid=l+r>>1,v=mid-1;
    int now=new_node(v);
    ch[now][0]=build(l,mid-1);
    ch[now][1]=build(mid+1,r);
    update(now);
    return now;
}
void dfs(int x)
{
    if (!x) return;
    pushdown(x);
    dfs(ch[x][0]);
    if (val[x]>=1 && val[x]<=n) printf("%d ",val[x]);
    dfs(ch[x][1]);
}
void res(int l,int r)
{
    int a,b,c,d;
    split(root,r+1,a,b);
    split(a,l,c,d);
    mark[d]^=1;
    root=merge(merge(c,d),b);
}
main()
{
    srand(time(0));
    scanf("%d%d",&n,&m);
    root=build(1,n+2);
    for (int l,r,i=1;i<=m;i++)
        l=read(),r=read(),res(l,r);
    dfs(root);
    puts("");
}
 

再甩一道模版题：bzoj1500

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮


20 COMMENTS

  1. attack2042017-07-11 下午4:11

    %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    厉害厉害

    [ 回复 ]
  2. Magolor2018-01-21 下午2:09

    请问一个问题，FhqTreap如何不按照关键字提取一个特殊点？

    即实现函数Split(x)，其中x为传入的这个点的编号(但整棵树不是以编号作为关键字的)

    例如【BZOJ2827 千山鸟飞绝】，需要将一个指定点从当前平衡树中分裂出，并插入到另一棵平衡树中

    [ 回复 ]
    • Magolor2018-01-21 下午3:03

      这道题好像明白了，可以按照指定点作为关键字，然后维护区间max就好了……

      但是就这个问题来说，请问怎么解决呢？

      [ 回复 ]
      • 远航之曲2018-01-21 下午4:32

        您的意思是知道这个点的下标？那应该可以直接找出值来split吧。。

        [ 回复 ]
        • Magolor2018-03-12 上午11:42

          不，就是只知道这个点的指针。
          例如文艺平衡树，如果不要求输出整个序列，而是每次询问i所在的位置(而不是位置i的值)。用Splay是可以做到的，不知道FhqTreap能不能做。

          [ 回复 ]
          • 远航之曲2018-03-12 下午8:58

            我以前也想过实现这个。。但是发现这样单独split后再单独merge，关键字就全乱了。。大概是不行的吧。。

            [ 回复 ]
    • thchuan20012018-01-24 下午10:17

      CZ!!!
      CZ!!!
      CZ!!!

      [ 回复 ]
  3. xxy2018-02-01 上午9:20

    请问文艺平衡树中build函数随机新节点的附加权值，如何保证它满足堆的性质

    [ 回复 ]
    • 远航之曲2018-02-01 上午10:02

      这样build出来树的深度是严格logn的，和一个一个插入得出的深度是一样的。其实应该是每次插入一个新点更好一些。。

      [ 回复 ]
  4. Fop_zz2018-02-12 下午3:15

    所以说对于维护区间和之类的像线段树一样就行了？

    [ 回复 ]
  5. Fop_zz2018-02-12 下午3:43

    文艺平衡树为什么要建到n+2

    [ 回复 ]
    • 远航之曲2018-02-13 下午3:01

      其实是新建了两个哨兵节点，作为dfs时候的终止标志。。现在想想好像也不大需要

      [ 回复 ]
      • Fop_zz2018-02-14 下午3:48

        好的谢谢

        [ 回复 ]
  6. functionendless2018-03-02 上午7:29

    不知道有没有人说过，但那张merge的GIF好像错了
    总树的第二个节点不应该是第二颗子树的吧

    [ 回复 ]
  7. cjZYZtcl2021-08-07 上午9:59

    GIF疑似挂了？

    [ 回复 ]
  8. 25192021-09-27 下午11:09

    能补下gif吗。。

    [ 回复 ]
  9. Fanrinin2022-02-10 下午2:58

    大佬，gif挂了能补一下吗

    [ 回复 ]
如果你觉的这篇文章不错，分享给朋友吧！

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
×