给自己看的。

摘要

fhq-Treap 的节点结构同样和 Treap 相同,通过给每个节点一个随机的权重,并保证整棵树从上到下的权重单调,以平衡树高。并满足所有 BST 的性质(左子树都小于自己,右子树都大于自己)。但 fhq-Treap 不通过旋转来改变自己的结构,而是通过 split-merge 这两个操实现。

split 操作是将某一棵子树分裂为两个子树,第一种方式是给出一个权值 k,要求分裂出的一棵子树的所有节点权值不超过 k,另一棵子树所有节点权值大于 k。第二种方式是给出一个子树大小 k,要求第一棵子树包含权值(或者下标)最小的 k 个节点,第二棵子树则是剩下的节点。

merge 操作这是将某两个子树,满足一棵子树的所有节点的权值都小于第二棵子树的所有节点的权值,给合并为一棵树。

节点结构

struct Tree {
    ll data; int rnd, cnt, v;
    Tree *l, *r;
};

cnt 表示的是节点的子树的大小,v 是这个节点代表的点的信息(具体而言,这个点的权值),data 是整个子树的信息。

l, r 分别是左右儿子的指针。

维护子树信息

其实就是合并左右儿子的子树和自己这个节点的信息。

例如 CF85D,要维护排序之后下标 \bmod5 \equiv x 的所有数的和,那么 pushup 函数是

void pushup(Tree *ret) {
    if (ret == null) return ;
    ret->cnt = ret->l->cnt + ret->r->cnt + 1;
    REP(d, 5) ret->sum[d] = ret->l->sum[d];
    ret->sum[(ret->l->cnt + 1) % 5] += ret->v;
    REP(d, 5) ret->sum[(d + ret->l->cnt + 1) % 5] += ret->r->sum[d];
}

首先子树大小 cnt 是必然需要维护的,并且就是两个子树的和加上自己的大小(这里由于不可重,所以为 1)。

接着考虑 d[i],表示 \bmod5\equiv i 的数的和。我们每个节点仅考虑自己这个区间内的数,因此我们发现,左子树中的所有节点,其在子树内的下标,和在现在这个区间内的下标是相同的(因为都是最小的几个数),因此可以直接继承。对于自己这个节点,那么他的下标由于是大于左子树的所有节点,小于右子树的所有节点,所以下标就是左子树的 cnt 加上 1。然后右子树的下标就有一个偏移量,为左子树的 cnt 加上 1,同样直接继承。

总之,我们需要考虑,合并左子树、自己这个节点、右子树。

Split

按权值分裂

void split(Tree *t, Tree *&l, Tree *&r, const int& k) {
    if (t == null) return l = null, r = null, void();
    if (k < t->v) r = t, split(t->l, l, t->l, k);
    else l = t, split(t->r, t->r, r, k);
    pushup(t);
}

考虑将树 t 分裂为权值不超过 k 的子树 l 和大于 kr

如果 t 已经指向空的东西,那么分裂出的两个子树都为空。

否则,如果 k 小于 t 的权值,那么我们可以发现,t 的右子树的所有点的权值都必然大于 k,那么右子树就不用再进行分裂了。

那么这个做法就是,直接把当前这棵树作为,分裂出来的右子树(这样就免去了拷贝右子树的过程),然后将左子树的分裂出来的结果,记为 x, yx 赋值给 l——因为 x 的权值不超过 k,其他子树都超过 ky 挂到 t 的左儿子上,因为这个时候 t 就是返回的 r,而 t 的左儿子中大于 k 的部分就应该代替原来的左儿子。

右儿子同理。

按大小分裂

void split(Tree *t, Tree *&l, Tree *&r, const int &k) {
    if (t == null) return l = null, r = null, void();
    if (t->l->cnt < k) l = t, split(t->r, t->r, r, k - t->l->cnt - 1);
    else r = t, split(t->l, l, t->l, k);
    pushup(t);
}

实际上递归和按权值分裂时相同的,不过递归的逻辑需要更改一下而已。

在分裂结束之后,一定要维护一下 t 的信息——因为我们这个写法每次的更改只涉及到 t 的子树,所以只需要维护 t 即可。

merge

Tree *merge(Tree *l, Tree *r) {
    if (l == null || r == null) return l == null ? r : l;
    if (l->rnd > r->rnd) return l->r = merge(l->r, r), pushup(l), l;
    else return r->l = merge(l, r->l), pushup(r), r;
}

merge 的逻辑同样很清晰。这个写法所维护的权重,是大根的,递减,如果左树的权重大,那么把右树和左树的右儿子合并上,并维护左树;否则将左树和右树的左儿子合并,并维护右树。

千万不要递归地去论证这两个函数是否 work,我们唯一要做的是 保证在边界条件正确,或在这一次递归时正确 即可,不要陷入套娃的思维误区。

其他操作

其他操作就把要操作的区间,split 出来,对这个节点进行某些修改,然后再 merge 回去即可。

None
上一篇 «
字符串学习笔记总览
» 下一篇