一、基本概念

线段树合并:将已有的两棵线段树合并为一棵,相同位置的信息整合到一起,通常是权值线段树比较裸的,就是将一棵线段树的每一个位置取出来插入另一棵中,但比较高效的线段树合并可以参照可并堆的合并方式

二、算法

假设两棵线段树树:

 

合并

  

线段树合并的原理:

对于两颗树的节点u和v

①如果u为空,返回v

②如果v为空,返回u

③否则,新建节点t,整合u和v的信息,然后递归合并u和v的左右子树

过程示例

 

三、代码

关键代码:

int merge(int u,int v){
    if (!u) return v;
    if (!v) return u;
    int t = ++cnt;
    sum[t] = sum[u] + sum[v];
    ls[t] = merge(ls[u],ls[v]);
    rs[t] = merge(rs[u],rs[v]);
    return t;
}

合并的复杂度取决于两棵线段树重合的部分的大小

每有一个位置权值同样存在,就要O(logn)的复杂度

不过,由于权值线段树中被更新的位置通常很均匀分布,所以合并的两棵线段树通常具有很小的相似性 

四、例题

https://www.luogu.org/problemnew/show/P3224

https://www.lydsy.com/JudgeOnline/problem.php?id=2733(题解:https://blog.csdn.net/weixin_43272781/article/details/95371733

五、参考文章

https://www.cnblogs.com/Mychael/p/8665589.html

https://www.cnblogs.com/owencodeisking/p/9965525.html

https://www.cnblogs.com/wozaixuexi/p/9365198.html

https://blog.csdn.net/keydou/article/details/83691189