### 什么是线段树合并
字面意思，合并两棵线段树和它存储的信息。
一般被合并的线段树都是**动态开点**线段树，这样才能保证复杂度。
> 显然，对于两颗满的线段树，单次合并操作的复杂度是 $O(n)$ 的。但实际情况下使用的常常是权值线段树，所有需要合并的线段树的总点数和 $n$ 的规模相差并不大。并且合并时一般不会重复地合并某个线段树，所以我们最终增加的点数大致是 $n\log n$ 级别的。这样，合并所有线段树总的复杂度就是 $O(n\log n)$ 级别的。当然，在一些情况下，可并堆可能是更好的选择。
> ——[来自OI Wiki](https://oi-wiki.org/ds/seg-merge-split/)
两棵线段树的区间结构必须匹配。即，两棵线段树的根节点对应的区间必须相同，各节点（或因为没有数据而留空的节点空位）对应的区间也必须相同。
假设把线段树B合并到线段树A上，那么刚合并后（不进行写操作）将会有几点性质：
- A的信息是B的信息与原A的信息的合并；
- B的信息保持原样。
而进行写操作后，将会有几点性质：
- 若对A进行写操作，大概率破坏B的信息，导致B无法再使用；
- 若对B进行写操作，大概率破坏A的信息，导致A无法再使用。
### 如何进行线段树合并
我们可以采用递归算法进行合并。设我们要把线段树B合并到线段树A上，那么从两个线段树的根节点开始递归，对于某个子节点（无论是左、右节点），有可能有几种情况：
#### A不存在这个子节点
那就把B的这个子节点的指针给A就好。
如果B也不存在这个子节点，那么合并后A的这个子节点的指针依然为0（不存在）；如果B存在这个子节点，那么合并后A的这个子节点就是B的这个子节点。
#### A和B都存在这个子节点
递归下去进行合并。
#### A存在这个子节点，B却不存在
无需合并，无需操作。
子节点合并完成后记得将父节点的信息更新为两棵子节点的合并信息。
### 关键代码
```cpp
struct Tree
{
int lo,ro;//左、右子节点的指针
int l,r;//本节点的区间
Data data;
int cnt;
}tree[MAXN*200];//空间开大一点为好
void combine(int o1,int o2)//将o2指向的线段树合并到o1上
{
if(tree[o1].l==tree[o1].r)//去到了叶子结点，那就将此节点的数据相加
{
tree[o1].data.v+=tree[o2].data.v;
return;
}
if(tree[o1].lo==0)//o1没有左子节点
{
tree[o1].lo=tree[o2].lo;//那就直接用o2的
}
else if(tree[o1].lo!=0&&tree[o2].lo!=0)//o1和o2都有左子结点
{
combine(tree[o1].lo,tree[o2].lo);//递归合并
}
if(tree[o1].ro==0)//右子节点同理
{
tree[o1].ro=tree[o2].ro;
}
else if(tree[o1].ro!=0&&tree[o2].ro!=0)
{
combine(tree[o1].ro,tree[o2].ro);
}
update(o1);
}
```
### 例题