FS OI
0%

FHQ_Treap 的优秀特性介绍和一个 C++ 实现

发表于 分类于 ，

Treap（树堆）是一种 OI 常用的平衡树结构，他结合了 BST（二叉查找树）和二叉堆的性质，并通过随机化让平衡树更加平衡，以达到优秀的查找和维护离散数据的效率。

常见的 Treap 写法需要旋转操作来维护平衡树的堆性质，这使得维持树形结构的方式略显复杂，而 FHQ_Treap 则去除了旋转操作，并更加符合平衡树所维护的线性拓扑结构，使得他在极大程度上扩展其功能的同时，代码量极低，这也是其相较于 Splay（伸展树）的优点。

FHQ_Treap 引入了子树的分裂和合并操作，使之在拓扑结构上更加贴近线性表（链表）的结构，而平衡树的快速查找优点也可以保留。据此，FHQ_Treap 还可以更加方便地维护区间信息，同线段树一样，因此线段树的区间类型 FHQ_Treap 都可以兼容。

基本操作：

  • 分裂：将一棵子树从其线性映射的某个位置分成两棵子树。
  • 合并：将两段不同的子树按照线性相连的方式合并成一棵新的子树。

FHQ_Treap 的堆性质的随机关键字是静态的（从该节点被创建起就不会改变），这一点特点更加利于我们在其中维护区间信息和调试。

用 FHQ_Treap 维护简单有序列表——实现 std::set 功能

由于需要维护 BST 和 Heap 的性质，每个节点分配如下资源：

  1. 数据 data：用于维护该位置的信息。
  2. 点权值 pri：用于维护随机化的堆性质。
  3. 左右指针 *ls *rs：用于指向该节点左右节点的资源地址。
  4. 子树大小 size：用于按位置分裂和查询。

观察每棵子树，他们所具有的如下操作都是一致的：

  1. 构造：随机分配点权值，分配该节点的数据，左右子节点的指针。
  2. 分裂：根据需要，可以分为按位置分裂和按值分裂。
  3. 合并：将两棵相邻的子树合并成一棵更大的新子树。

据此，我们可以大致定义出这个子树类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename T>
class node {
    T data;
    int pri, size;
    node *ls = NULL, *rs = NULL;

    /* construction */
    node(const T &x) : data(x), size(1), pri(rand()) {}
    
    /* split */
    /* pos */ pair<node*, node*> split(int p);
    /* val */ pair<node*, node*> split(const S &v);

    /* merge */
    static node *merge(node *l, node *r);
}

注意到每次修改之后的子树大小等信息可能会发生改变，因此我们定义一个函数用于处理这些变化：

1
2
3
4
5
void flush() {
    size = 1;
    if(ls) size += ls->size;
    if(rs) size += rs->size;
}

在构造函数中加入 flush() 以更新当前节点的信息。

1
2
/* construction */
node(const T &x) : data(x), pri(rand()) { flush(); }

分裂

按值分裂:

1
2
3
4
5
6
7
8
9
10
11
12
pair<node*,node*> split(const S &v) {
    release();
    if(val <= v) {
        auto split = ls->split(v);
        ls = split.second; flush();
        return {split.first, this};
    } else {
        auto split = rs->split(v);
        rs = split.first; flush();
        return (this, split.second); 
    }
}

按大小分裂：

由于我们在实现这种可以分裂的树的时候不可避免地直接操作指针，因此为了代码简洁和防止非法指针操作，定义函数 get_size 来获取一个指针对应的子树的大小：

1
2
template <typename T>
int get_size(node<T> *x) { return x?x->size:0; }
1
2
3
4
5
6
7
8
9
10
11
12
pair<node*,node*> split(int p) {
    release();
    if(get_size(ls) < p) {
        auto split = ls->split(p);
        ls = split.second; flush();
        return {split.first, this};
    } else {
        auto split = rs->split(p-get_size(ls)-1);
        rs = split.first; flush();
        return (this, split.second); 
    }
}

合并

1
2
3
4
5
6
7
8
9
10
static node *merge(node *l, node *r) {
    if(!l || !r) return (l?l:r);
    if(l->pri > r->pri) {
        l->rs = merge(l->rs,r);
        return l->flush(), l;
    } else {
        r->ls = merge(l,r->ls);
        return r->flush(), r;
    }
}

这样我们就实现了 std::set 的基本功能。

区间维护

FHQ_Treap 的优势主要体现在其区间操作上，我们仿照线段树的定义形式，给这棵平衡树添加区间信息的维护方式。

变更

  1. 添加 seg 信息表示子树对应区间。
  2. 添加 release() recieve() modify() query() 等线段树功能函数。
  3. 在 flush() 中添加对区间信息的维护。
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
template <typename S, typename L>
struct node {
    int pri, size;
    S seg, val; L tag;
    node *ls = NULL, *rs = NULL;
    void release() {
        if(ls) ls->recieve(tag);
        if(rs) rs->recieve(tag);
        tag = L();
    }
    void recieve(const L &v) {
        seg.apply(v); val.apply(v);
        tag = L::merge(tag,v);
    }
    void flush() {
        seg = val, size = 1;
        if(ls) seg = S::merge(ls->seg,seg), size += ls->size;
        if(rs) seg = S::merge(seg,rs->seg), size += rs->size;
    }
    static node *merge(node *l, node *r) {
        if(!l || !r) return (l?l:r);
        if(l->pri > r->pri) {
            l->rs = merge(l->rs,r);
            return l->flush(), l;
        } else {
            r->ls = merge(l,r->ls);
            return r->flush(), r;
        }
    }
    void print(string base) {
        if(rs) rs->print(base+"   |");
        cout << base << "---" << val << "-[" << seg << "]-(" << tag << ")-<" << size << ">----{" << pri << "}\n";
        if(ls) ls->print(base+"   |");
    }
    node(const S &x) : pri(rand()), size(1), val(x), tag() { flush(); }
    void modify(int s, int e, const L &v, int _begin = 1) {
        if(s <= _begin && size <= e-_begin+1) { recieve(v); return; }
        release();
        if(ls && s <= get_size(ls)) ls->modify(s,e,v,_begin);
        if(s <= _begin+get_size(ls) && _begin+get_size(ls) <= e) val.apply(v);
        if(rs && e >= _begin+get_size(ls)+1) rs->modify(s,e,v,_begin+get_size(ls)+1);
        flush();
    }
    S query(int s, int e, int _begin = 1) {
        if(s <= _begin && size <= e-_begin+1) return seg;
        release();
        if(ls && s <= get_size(ls) && e > _begin+get_size(ls))
            return S::merge(S::merge(ls->query(s,e,_begin),val),rs->query(s,e,_begin+get_size(ls)));
        if(s <= get_size(ls)) return ls->query(s,e,_begin);
        if(rs && e >= _begin+get_size(ls)+1) return rs->query(s,e,_begin+get_size(ls)+1);
    }
    pair<node*,node*> split(const S &v) {
        release();
        if(val <= v) {
            auto split = ls->split(v);
            ls = split.second; flush();
            return {split.first, this};
        } else {
            auto split = rs->split(v);
            rs = split.first; flush();
            return (this, split.second); 
        }
    }
    pair<node*,node*> split(int p) {
        release();
        if(get_size(ls) < p) {
            auto split = ls->split(p);
            ls = split.second; flush();
            return {split.first, this};
        } else {
            auto split = rs->split(p-get_size(ls)-1);
            rs = split.first; flush();
            return (this, split.second); 
        }
    }
};
template <typename S, typename L>
int get_size(node<S,L> *x) { return x?x->size:0; }

另：FHQ_Treap 显然具备良好的可持久化条件，读者可以思考如何利用已有的代码实现可持久化的数据结构。（提示：可以从指针的变化情况来考虑，不需要修改现在的函数内容就可以实现）

总结

FHQ_Treap 是一种优秀的数据结构，本文探讨了其结构的优秀特征，并探讨了他在区间信息维护上的优势，并提供了代码各部分的解析。

希望本文能够引发读者的思考，并给读者带来关于 FHQ_Treap 的更多理解。