引言

有一类经典的数据结构问题，要求高效地支持以下几种操作：

1.新建一个数据结构

2.将两个数据结构的信息合并（要求合并操作满足交换律、结合律）

3.在数据结构中查询某些信息

这类问题有时需要根据数据结构的特性设计操作，同时也存在一类较为通用的解决方法。

合并操作可以看做批量地在数据结构中添加信息，而一般的插入操作则是合并的特例

定义与约定

设n表示问题中新建的数据结构个数

|A|表示数据结构A由几个数据结构合并得到

A+B表示合并A,B得到的数据结构，因此有|A+B|=|A|+|B|

直接合并

当合并两个数据结构时，可以将其中一个数据结构的信息逐一插入到另一个数据结构中，总共需要进行O(n^2)次插入操作。

基于某些特殊性质的合并

森林实现的并查集可以直接通过修改父亲合并

无旋转treap可以基于分裂操作递归合并，若两树值域区间不相交也可以用类似斜堆的合并方式

各种可并堆也设计了相应的方式进行高效的合并

此类合并一般非常高效，一部分还能同时在非均摊的意义下保证很低的合并复杂度，但一般难以推广。

启发式合并

若在合并A,B时，令|A|<=|B|，将A拆散并逐一插入B，由于每次插入会使一个元素所在数据结构增大至少一倍，可以将插入操作的次数降至O(nlogn)。

平衡树启发式合并是一个常见的例子。

基于相同结构的合并

对于两个结构相同的数据结构，可以考虑将两个数据结构重叠起来，合并重叠部分的信息。

一个简单的例子是trie的合并，将两棵待合并的trie重叠起来，从根开始dfs求出重叠部分并合并相关信息。合并的时间复杂度与合并时重叠部分的大小有关，由于重叠部分合并后总点数减少了，可以保证总的时间复杂度与合并时减少的点数同阶。

对于线段树或k-d树，如果采用相同的区间划分方式，也可以使数据结构的结构相同，从而可以应用这个方法。

此方法一般优于直接进行启发式合并。

例题 2014年集训队互测 bzoj3615 MSS

题目大意 维护一些平面上的点集，支持按某一维坐标分割点集，合并两个点集，对一个点集的所有点点权加上一个数，询问一个点集的点权和、最小/大值。

对给出的点建立二维k-d树，建树后将每个点到根的路径提取出来得到n棵只包含一个点的相同结构的k-d树。合并操作可以很方便地递归进行，点权的维护可以仿照线段树打标记实现。分裂操作可以看作合并的逆操作，由于k-d树的结构，可以保证分裂时增加点数为O(n^(1/2))。

基于二进制分组的合并

某些时候，不能高效地在数据结构中插入一条信息，这时候便很难应用前文所提及的方法。如果对A+B的一次查询可以转化为对A,B分别查询，那么可以平衡合并和查询的时间复杂度，在合并时不完全合并，以增加查询的复杂度为代价减少合并次数。

对于数据结构A，可以将|A|表示为一些互不相同的2的非负整数次幂之和（至多分为O(log|A|)个数），并将信息分别维护，查询时在O(log|A|)个部分内分别查询。在合并时，仿照二进制加法的进位过程，合并对应的部分。这样一个元素每参与一次合并，所在数据结构的大小增大一倍，若合并A,B的时间复杂度为O(|A|+|B|)，则合并操作的总时间复杂度为O(nlogn)，优于直接对二进制分组套用启发式合并。

数据结构的合并