浅淡线段树合并

线段树，是信息学比赛中一种强有力的数据结构；
动态开点，让线段树在数据范围上挣脱了束缚；
线段树合并，让树上问题获得了升华。

前言

线段树合并的基础——动态开点线段树
在初学线段树的时候，一般都会开四倍空间，并且根据二叉树的特性，让左右孩子是右移一位和右移一位加一。
但假如说题目变成这样：

请你维护一个可重集合三种操作
1.加入一个数
2.删除一个数
3.统计集合中有多少数在 \([l,r]\) 之间
数字值域：\(n\in[1,10^{12}]\)，操作数 \(10^5\)

很显然，我们会发现这个时候开和值域一样的空间，很明显会挂掉。我们会发现，操作数只有 \(10^5\) ，最多只会出现 \(10^5\) 个不同的数。所以……
离散化
很好，我们接着往下看：

本题强制在线

那我们就没有办法了么？
和刚才说的一样，只会出现 \(10^5\) 个不同的数，对于我们的线段树，其中有值的最多只有 \(10^5*log_2(10^{12})\) 个，如果我们能够只开这些点，那就好了。
那么，我们在程序最开始假象有这样一颗“线段树”，范围是值域的普通的线段树，它的每一个值都是零，但是我们并不需要实际开出来——因为我们知道他们都是零。
每当我们要修改一个点的值的时候，我们给他开一个实在的空间，存储修改之后的值，这样，我们的空间就是可接受的了。

这是最开始的，线段树上每一个黑色的节点都是零，但我们并没有给它开实际的空间。

当我们要修改这个标蓝的点的值得时候，我们就把这条链上所有我们要访问并修改的点开一个实际的空间，并存储修改后的值。
由于我们对于每一个点都是动态开的，这样的线段树并不满足下标的性质，所以我们要在同时记录它的左右儿子。
如果记录了左右儿子，询问就很简单了——如果儿子是空，说明这个孩子的子树都是空的了。
如下图，绿色边是记录了孩子的值，紫色的边表示这边的孩子是空，还没有被修改过值。

这样，我们和一般的线段树的区别就是：修改空点时要开新点；查询值时要判是否为空。

原理

既然我们知道了线段树合并的基础，那么怎么线段树合并就是很显然的：
如果我要将两个动态开点的线段树合并起来，就是尽可能利用他们的空间，处理他们
很显然，他们合并需要的空间一定小于他们两个一共有的空间，而且在最初的那颗“线段树”之中的位置也是不会变的。
那么我们就要处理的是——如果有一个位置，两个树都有空间，我们应该怎么办？
先递归合并他们的左右孩子，然后合并这两个点的值，然后删除掉其中一个点。

int merge(int &pos1,int pos2,int l,int r)
{
  if(pos1&&pos2)//左右孩子都有值
  {
    merge(s[pos1].lson,s[pos2].lson,l,mid);//合并左孩子
    merge(s[pos1].rson,s[pos2].rson,mid+1,r);//合并右孩子
    merge_num(pos1,pos2)//合并这两个节点的值
    //delete_xds(pos2)删除节点pos2，一般不会用
  }
  else pos1+=pos2;//相当于让pos1等于两个数中不为零的那个
  return;
}

优势

线段树合并的代码看着似乎比较简单，那它的优势在哪里呢？
首先，它一定有线段树的有点，能够在 \(O(logn)\) 的复杂度之内进行修改和查询。
其次，它在合并的复杂度是很严格的：无论你要进行多少次线段树合并，它的复杂度一定等于你合并过程中所有删除的点的数量。
如果我们把是否两个点都有值移动到递归函数的外面，那么我们调用merge()的次数是等于我们要合并的次数等于我们要删除点的数量。
由于一般线段树合并的题目，一共需要的线段树的点一般是 \(nlogn\) 或者 \(mlogn\) 个，那么线段树合并的复杂度的上限是严格 \(O(nlogn)\) 的
拥有一个稳定的复杂度，是一个常规算法比较重要的一点
而且，如果 \(O(nlogn)\) 的复杂度是可以接受的，那么十有八九这道题稳了。

线段树合并解决树上问题

为什么线段树合并一般都是处理树上问题或者树形问题的呢？
很显然，合并两个线段树之后，里面必然会有一颗线段树报废掉。
我们最开始有 \(n\) 颗线段树，就只能最多合并 \(n-1\) 次。\(n\) 个节点 \(n-1\) 条边，这就是树。
能用线段树合并优化的题目，一般都是要你对于一个区间里的状态进行统计，就是那些一眼觉得可以用线段树维护的答案（不考虑在不在树上的问题）

而一般的树形问题都会有一个特点——父亲的信息和状态可以从孩子的状态转移过来，甚至是直接继承。那么如果能够在DFS子树的过程中，处理所有孩子的信息就可以。
子树之间是相对独立的，子树的信息也是满足加法的，对于一些情况就可以用线段树合并的。
因为我们用了线段树合并，这个过程的复杂度就是严格 \(O(nlogn)\) 的，不会因为树的形态而有过大的浮动。
无论是链，还是菊花图，或者是满树，它都是 \(O(nlogn)\) 的。
如果用线段树合并是正确的，它就不可能被出题人卡掉。

例题

接下来就是喜闻乐见的栗子时间~~~

1. Luogu P4556 [Vani有约会]雨天的尾巴
   首先这道题肯定是在树上遍历解决问题（这不是废话么），同时，我们需要维护的是一个带增加与删除的最大值。
   能够带修地维护最大值，我们自然而然地会想到用线段树维护，由于是在一条路径上同意放一次救济粮，那么一个节点发放的救济粮状态就是和子树直接相关的，所以可以考虑用动态开店线段树维护，用线段树合并来合并。
   知道了怎么维护，我们还需要考虑怎么处理救济粮的发放，如果我们单纯地在两个端点上加一个救济粮，就会出现一个问题：这两个端点所有公共祖先都会被发放两次这种救济粮，但是除了LCA上应该有一袋，其他的都不应该有的。
   意识到这一点，解决问题的方法也就出来了：在它们的LCA和LCA的父亲分别减一袋这种救济粮，也就是加-1的救济粮即可。
   2.CF600E Lomsat gelral
   很显然，线段树是维护区间内众数的一个强有力方法（请不要和我说分块，谢谢），所以不能发现可以用线段树统计答案，然后发现父亲的线段树就是把所有的孩子合并起来，再给其中的某一个值加一即可。
   3.CF570D Tree Requests
   我们不难发现用线段树合并很容易能够统计出子树中深度的k的点中，每个字母出现多少次，因为需要统计是否能形成回文串，所以我们要观察回文串的结构：至多只有一个字符会出现单个的，所以我们可以用一个long long来进行状态压缩，可以用亦或和来完成字数的合并。
   4.疑似原创题：

现在有一个带权无向联通图，定义dis(u,v)为，图上u,v两点的所有路径中，路径上权值最大的边的最小值
询问若干对dis(u,v)的值，不强制在线

易证，dis(u,v)必然在图的最小生成树上，所以考虑在最小生成树的过程。
如果对于某一个询问的两个点，他们在加某一条边的时候进入了同一个并查集，所以这一次加的边的权值就是它的最大值。
我们考虑将所有在同一并查集里面的点的所有未处理的询问统一放到他们的公共大爹爹那里去。
在合并并查集的同时合并处理询问的线段树，当在某一次的合并时，合并到了某一个叶子，也就意味着这个询问就找到答案了。
这个算法的复杂度是O(mlogn+QlogQ)的，比较离谱的log询问算法……

线段树合并优化DP

线段树合并可以维护树上问题，它也是可以优化树上DP的，这个优化我在DP的各种优化小结中提到过，这里就不再赘述。