数据结构 Trick 之：平衡树有交合并

· · 算法·理论

能解决的问题类型

需要将两个值域有交可重集合并的问题。

优缺点

无

思路

这个 Trick 基于 FHQ。

首先，让我们回顾一下 FHQ 的 merge：

int merge(int l, int r) {
    if (node[l].randd <= node[r].randd) {
        pushdown(l);
        node[l].rs = merge(node[l].rs, r);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        node[r].ls = merge(l, node[l].ls);
        pushup(r);
        return r;
    }
}

我们知道：这个东东只能解决不交合并，但是，我们可以受此启发。

我们在做不交合并是，将一整颗树和一个子树合并，就像这样： 那么我们是不是可以将其中一棵树分成两半，分别合并呢？（如下图） 这个合并复杂度几乎 O(n\log n)，极端情况下才会到 O(n\log^2 n)，证明可以看这个。

流程

  1. 找到 randd 小的那个根作为合并之后的树根。
  2. 将 randd 小的那个树按总树根进行分裂。
  3. 分裂左边跟总根的左子树合并，右边跟总根的右子树合并

    例题与代码

    P3224 [HNOI2012] 永无乡

P5494 【模板】线段树分裂

由于其他的都是普通平衡树，就只放这个函数了。

int Merge(int l, int r) {
    if (!l || !r) return l | r;
    int L, R;
    if (node[l].ran <= node[r].ran) {
        pushdown(l);
        split(r, L, R, node[l].v);
        node[l].ls = Merge(node[l].ls, L);
        node[l].rs = Merge(node[l].rs, R);
        pushup(l);
        return l;
    } else {
        pushdown(r);
        split(l, L, R, node[r].v);
        node[r].ls = Merge(node[r].ls, L);
        node[r].rs = Merge(node[r].rs, R);
        pushup(r);
        return r;
    }
}