线段树合并与分裂是线段树常规技巧，用于权值线段树维护可重集，考虑空间复杂度，线段树合并要使用“动态开点”。

线段树合并

线段树合并基本思想：递归合并左右子树，更新根节点。

递归边界：当左右子树有一个为空，返回另外一个非零结点编号。或者，当前管理区间长度为 $1$ , 将维护信息合并，返回。

线段树合并核心代码：

int merge(int a,int b,int l,int r)  //线段树合并
{
    if(a==0||b==0)return a+b;
    if(l==r)
    {
        //做合并的事
        //将 b 中的值加入 a 线段树中
        // 例如 t[a].sum+=t[b].sum;  
        return a;
    }
    int mid=(l+r)>>1;
    t[a].ls=merge(t[a].ls,t[b].ls,l,mid);
    t[a].rs=merge(t[a].rs,t[b].rs,mid+1,r);
    pushup(a);
    return a;
}

线段树合并复杂度

对于单次合并，如果两棵线段树都是满的情况下，单次合并复杂度就是 $T(n)=2 \times T(\frac{n}{2})+1$，即 $O(n+\log{n})=O(\log{n})$ , 但是由于大多数情况下线段树并未放满，如果之前总共单点修改了 $m$ 次，每次修改将增加 $O(\log{n})$ 个节点，总节点数是 $O(m\log{n})$ ,合并线段树，相当于将这些节点都访问一次，那么线段树合并的时间复杂度就是 $O(m \log{n})$ , 整个空间复杂度也是 $O(m \log{n})$ , 实际情况数组开到 $4*M*20=80*M$ (取 $(\log{n})$ 为 $20$)就可以了。

P4556【模板】线段树合并

【题意简化】给定 $n(\le 10^5)$ 个节点的一颗树，$m(\le 10^5)$ 次修改，对于树上 $x->y$ 的链上每个节点 $z(\le 10^5)$ 类型加 $1$ ，修改结束后，询问每个节点类型最多的编号。

【分析】对于树上每个节点，维护每种类型的数量和数量最多的类型，线段树下标表示类型，维护最大值和对应的下标。

利用树上点差分，链上修改，转换为 $4$ 位置上单点修改。修改结束后，对于每个节点，将儿子对应的线段树合并进来。

参考代码：点击

学习完毕

{{ select(1) }}

• YES
• NO