一、基本概念
线段树合并:将已有的两棵线段树合并为一棵,相同位置的信息整合到一起,通常是权值线段树比较裸的,就是将一棵线段树的每一个位置取出来插入另一棵中,但比较高效的线段树合并可以参照可并堆的合并方式
二、算法
假设两棵线段树树:
合并
线段树合并的原理:
对于两颗树的节点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