浅谈线段树合并

本篇随笔浅谈一下线段树合并。

一、前置知识

线段树合并的前置知识有普通线段树、权值线段树、动态开点。

分别附上讲解博客：

二、线段树合并的概念

线段树合并，字面意思就是概念，把两棵动态开点的权值线段树合并到一起。

其实普通线段树也是可以线段树合并的（当然也是动态开点），但是合并之后的意义不太大。

这样，把两棵线段树维护的信息相合并，最终可能会达到一些book思议的效果。

三、线段树合并的方式

线段树合并有两种方式：第一种方式是把一棵线段树合并到另一棵线段树上。第二种方式是把两棵线段树合并后建立一棵新树。

如果采用第二种方式的话，那所有的线段树都合一遍，空间肯定会炸。所以我们在选择第二种方式的时候，要考虑动态开点。

但是还是考虑第一种方式，如果我们合并之后，原树就没有用了，那完全可以用第一种方法，更节约一些。

那么，我们在合并两棵线段树的大致方式就是这样的：我们现在要合并一棵根节点编号为\(x,y\)的线段树，并且把合并后的结果直接赋到x这棵线段树上。

首先，因为动态开点，有些节点可能不一定儿女双全。所以，当前的\(x,y\)并不一定都有值，如果没有的话，就直接把还有的节点赋给新树即可。

然后递归合并即可。合并编号之后，再合并节点维护的信息。

代码：

void merge(int &x,int y)
{
    if(!x||!y)
    {
        x=(!x?y:x);
        return;
    }
    merge(lson[x],lson[y]);
    merge(rson[x],rson[y]);
    pushup();
}

四、线段树合并的时空复杂度

线段树合并有的时候会给人一种很暴力的感觉，很多情况都不太敢用，所以在这里简单证明一下它的时空复杂度。

首先，根据上面的实现方式，显然，对于两棵要合并的线段树来说，我们只需要合并它俩的重合节点数。而这个交集节点最多也就是较小的那棵线段树的节点数。也就是说，当我们完成所有的合并操作的时候，一共也只合并了最大节点个数次。

那么根据动态开点，最大节点个数不可能超过\(m\log n\)其中m是操作数，n是区间长度。这也就保证了其时间复杂度。

空间复杂度因为是动态开点，是同样的\(O(m\log n)\)。

也就是说，动态开点大法保证了其时空复杂度的正确性。