线段树进阶

分裂与合并

对线段树的结构进行操作，实现对所维护信息的快速合并与提取。

核心：权值线段树，动态开点。

线段树合并

顾名思义，将两颗线段树合并为一颗，对应节点所维护信息相加。

int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y;//如果其中一者为空，则可以直接合并
    ch[x][0] = merge(ch[x][0], ch[y][0]);
    ch[x][1] = merge(ch[x][1], ch[y][1]);
    val[x] += val[y];//合并两节点信息
    return y;
}

需要注意的是，上文是一个基础的实现。在合并的过程中，x原本保存的信息被覆盖了。因题而异的，可能存在：需要保留x,y的完整信息，需要清空信息实现内存回收的一些细节。在此不表。

考虑一下复杂度，令（所有操作涉及的）总节点数为 $n$，值域大小为 $U$
对于执行一次merge操作，令两棵树重合（都拥有）的节点个数为 $m$，则复杂度为 $O(m)$

对于所有操作（假设我们最终合并成了一棵树），考虑到插入每个叶子节点会创造出 $O(log_U)$ 个新节点，显然总复杂度不会超过最初的节点数的和（因为在某次合并过程中，如果其中一者为空，就不会继续下去，所以只有两个节点都存在才会贡献复杂度），则总复杂度为 $O(nlog_U)$

*时空复杂度相同

**注意常数

一个例题：Luogu P3521

给定一颗有 $n$ 个叶节点的二叉树。每个叶节点都有一个权值 $p_i$（注意，根不是叶节点），所有叶节点的权值构成了一个 $1 \sim n$ 的排列。
对于这棵二叉树的任何一个结点，保证其要么是叶节点，要么左右两个孩子都存在。现在你可以任选一些节点，交换这些节点的左右子树。在最终的树上，按照先序遍历遍历整棵树并依次写下遇到的叶结点的权值构成一个长度为 $n$ 的排列，你需要最小化这个排列的逆序对数。

*先序遍历：中左右

考虑到对于交换操作，不会影响树的其他部分关于这个子树的逆序对数。

那么可以贪心，只需自底向上的决策，使得每次产生的逆序对树最小即可。

问题转化为维护若干个集合，支持：

1.快速计算两个集合相对逆序对个数
2.集合合并

一个显然的选择是set+启发式合并，同时更显然的是复杂度为$O(nlog^2_n)$

显然用权值线段树合并就是一个log的了。

线段树分裂

听起来很像线段树合并的逆操作，实际上还是有一定区别的。

即按照排名k（或者权值 k）将线段树分裂为两颗。

void split(int x, int y, int k) {
    int tmp = sum[ch[x][0]];//左儿子内点的个数
    if (k > tmp) split(ch[x][1], ch[y][1] = newnode(), k - tmp);//如果左儿子节点个数不够，全部保留，进入右儿子
    else swap(ch[y][1], ch[x][1]);//够了的话就把右儿子切断（给树y）
    if (k < tmp) split(ch[x][0], ch[y][0] = newnode(), k);//递归左儿子
    //执行完毕后更新信息
    sum[y] = sum[x] - k;
    sum[x] = k;
}

考虑复杂度，显然是单次 $O(log_U)$ 的。
考虑对 merge 操作的影响，每次最多新增$O(log_U)$个节点（一个叶子节点），若执行了 $m$ 次，merge总复杂度增加$O(mlog_U)$

仍然可以接受。

经典例题：Luogu P2824

给出一个长度为 $n$ 的排列，对于$m$ 次操作，分别为对某个区间升序/降序排序。

输出最后下标 $q$ 上的数是什么。

原题有经典的离线+二分答案做法，在这里我们加强一下，要求强制在线。

对初始的每个节点维护一个权值线段树，那么排序操作即合并一些线段树。由于被排序后的区间一定是有序的（经典废话），那么实际上哪个数在哪里都是知道的。

如果合并的过程中需要某棵线段树中的一部分信息怎么办？

线段树分裂即可。

线段树分治

有单独的课件。