专栏文章

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

pporse
算法·理论参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqh4k4y
此快照首次捕获于
2025/12/04 04:42
3 个月前
此快照最后确认于
2025/12/04 04:42
3 个月前
查看原文

能解决的问题类型

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

优缺点

无

思路

这个 Trick 基于 FHQ。
首先，让我们回顾一下 FHQ 的 merge：
CPP
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(nlog⁡n)O(n\log n)，极端情况下才会到 O(nlog⁡2n)O(n\log^2 n)，证明可以看这个。

流程

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

例题与代码

P3224 [HNOI2012] 永无乡
P5494 【模板】线段树分裂
由于其他的都是普通平衡树，就只放这个函数了。
CPP
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;
	}
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...