本人的博客园，可能更好的体验。

前言：

模拟赛考到了此类题目，出现过很多次了，就去小小学习了一下，发现其实挺简单的。

前置知识：

1. 线段树：这个知识点如果没有掌握先自行学习，学完再来看，因为本人太弱了，没有写这个的讲解。

2. 动态开点线段树：这个知识点如果没有掌握先自行学习，学完再来看。

引入：

在一些树形结构中子节点的贡献要上传到父亲节点时，一些关于子树信息需要用到线段树维护的上传时就需要合并当前所有子节点的线段树信息，但是线段树是一棵满二叉树，如果直接去合并的话时间复杂度肯定不优，所以线段树合并就应运而生了。

正文：

讲解：

首先我们知道如果两棵树中扫同一个位置的节点时如果有一棵线段树没有当前节点的话，那么新树的当前节点直接是有值的即可。而如果两个都有的话就继续往下搜，直到搜索到没有值的或者是叶子结点（和合并两棵平衡树很相似，但是这里左右儿子都需要去合并，而不像平衡树可以只合一半）。

时间复杂度证明：

对于时间复杂度的分析，因为我们知道只有两棵线段树的公共部分我们才会去合并，其他的情况都不需要（如下图中我们就只需要往下扫左右儿子合并的位置是 1，2，3，其他的直接合并即可）。

那么时间复杂度其实就是两棵子树的公共部分，综合时间复杂度是 O(N\log {V})，V 是值域大小，值域小时可以放心大胆的使用。

实现方式：

首先我们先来讲一下比较简单的类型，如果我们需要合并两棵线段树，在保留原来的两棵线段树还存在的情况下合并出来一个新的线段树。这样是十分简单的，先看一张图：

我们如果要合并这两棵线段树的话，那么首先考虑把相同的节点直接放到一个节点上（如下图中 1 这个节点两个都有，我们就建一个新一，作为新线段树的根节点），若合并到某一个节点时有一棵树没有了，就直接把有值的点的下标连向新建的上位节点即可（比如下图中 7 这个节点左边的线段树中就没有，就可以直接把新 3 节点的右子节点连向这个 7 的下标即可，然后就不用合并他的子树了，没必要，毕竟这个节点下的值在当前节点已经做完了，没有新的修改）。

代码

void merge(int &z,int x,int y,int l,int r){
    if(!x||!y){z=x+y;return;}//有一棵子树当前位置没有值，就把有值的连上去
    z=++cnt;//否则新建一个节点
    if(l==r){return;}//如果当前区间长度为一就退出，当然在不同题中有不同的维护也要处理，比如下文中的模版题就要维护加
    merge(tr[z].ch[0],tr[x].ch[0],tr[y].ch[0],l,mid)；//合并左右节点
    merge(tr[z].ch[1],tr[x].ch[1],tr[y].ch[1],mid+1,r);
    //如果有需要上传一些值就按线段树普通上传
} 

\\

上面的方式固然可行，但是空间上还是不怎么优秀。如果我们合并线段树后这两棵线段树就没有用了，那么其实我们不需要新开一个节点，直接维护到一棵树上即可（如上图中的 1 号节点就没必要新建一个节点，直接用左子树的就可以了，若左边没有但右边有，就像 7 号节点，就直接把他连向左子树同样位置他的父亲，然后就不用合并他的子树了，没必要，毕竟这个节点下的值在当前节点已经做完了，没有新的修改）。

代码

void merge(int &x,int y,int l,int r){
    if(!x||!y){x+=y;return;}//有一棵子树当前位置没有值，就把有值的连上去
    //和上面唯一的区别就是不用新建节点浪费空间了，但有些如果用来合并的子树还会被调用就不能这么写了
    if(l==r){return;}//如果当前区间长度为一就退出，当然在不同题中有不同的维护也要处理，比如下文中的模版题就要维护加
    merge(tr[x].ch[0],tr[y].ch[0],l,mid);//合并左右节点
    merge(tr[x].ch[1],tr[y].ch[1],mid+1,r);
    //如果有需要上传一些值就按线段树普通上传
} 

板题讲解：

雨天的尾巴 /【模板】线段树合并 - 洛谷

讲解：

这道题首先我们会发现我们可以给每一个点开一棵线段树，记录不同的救济粮有多少。那么答案显然就是这棵线段树中数值最大的点的下标。但是如果直接这样去写，不仅空间复杂度会爆炸，时间复杂度也会爆炸。这样的情况下我们考虑树上差分（和普通差分差不多，就是放到了树上）。在当前需要加的两个端点线段树上加贡献，发现如果一直贡献上传父亲到二者的 lca 就不用了，所以我们只用在 lca 以及他的父亲上删除贡献就可以了。

这样记录之后直接一遍深搜，把儿子节点的贡献上传父亲，用线段树合并即可。

代码在这里（码风有点丑，不喜勿喷）。

\\

P3605 [USACO17JAN] Promotion Counting P

讲解：

按照值去给每一个人建一棵线段树，然后答案就很显然是查询比当前节点大的有几个，直接把当前节点的子节点线段树合并到当前的节点上，然后直接查询即可，感觉上比模版题还要简单一点，少了区间赋值的操作。

代码在这里（码风有点丑，不喜勿喷）。

\\

Lomsat gelral - 洛谷

讲解：

这道题呢也是版子题，给各位练练手，熟悉模版。我们可以直接个每个节点开一棵线段树，然后每一个单点呢就表示每一种不同的颜色的数量，上传是很好写的，左儿子和右儿子中颜色数量的最大值累计进当前节点即可（相等的话两个只都要加进去）。想完线段树这道题也就差不多了，直接子树贡献用线段树合并到父亲节点，然后统计答案即可。

代码在这里（码风有点丑，不喜勿喷）。

\\

[POI2011] ROT-Tree Rotations - 洛谷

讲解：

这道题的思路很简单，首先是一个性质，我们转动一个子树对于这个子树的整体贡献其实并没有什么影响，那么交换子树的影响其实只有从左子树到右子树的贡献。那么考虑计算两个值，一个是位置关系不变，一个是交换子树。我们知道逆序对个数就是一个数字前面有几个比他大的加起来，那么有一个比较好的求逆序对思路就是在值域线段树上，一个节点的左子树大小乘右子树大小（左边的节点一定比右边的小，而左右分别的贡献在自己的节点中已经处理完了，只剩下从左到右的要处理），而我们又知道如果没有值的话是不用处理的，那么维护这个的复杂度其实是和线段树合并等价的（在合并的时候统计两棵子树在当前节点的贡献即可），那么直接上线段树合并，就可以了。

然后这道题的细节就十分复杂了。在这道题上的空间上卡的非常死，需要注意数组大小以及开的类型对空间的影响，这就是本题最恶心的地方了。

代码在这里（码风有点丑，不喜勿喷）。