线段树合并与线段树分裂

线段树合并与线段树分裂

参考资料：

1

线段树合并

流程

线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护树上或是图上的信息。

我们要使用动态开点这个技巧。

线段树合并流程如下：

1. 如果两颗线段树都没有此节点，将此节点赋值为 $0$，递归结束。
2. 如果只有一颗线段树有此节点，直接将此节点赋值为它，递归结束。
3. 如果此节点是叶子节点，暴力合并，递归结束。
4. 如果两颗线段树都有此节点，递归合并左右儿子，然后 pushup。

伪代码如下：

	void merge(int &x,int y,int l,int r){
   
		if(!x&&!y)
			return ;
		if(!x||!y){
   
			x=x+y;
			return ;
		}
		if(l==r){
   
			//做些什么
			return ;
		}
		merge(ls(x),ls(y),l,mid);
		merge(rs(x),rs(y),mid+1,r);
		pushup(x);
	}

复杂度：

显然，对于两颗满的线段树，合并操作的复杂度是 $O(n\log n)$ 的。但实际情况下使用的常常是权值线段树，总点数和 $n$ 的规模相差并不大。并且合并时一般不会重复地合并某个线段树，所以我们最终增加的点数大致是 $n\log n$ 级别的。这样，总的复杂度就是 $O(n\log n)$ 级别的。

例题

luogu4556

一棵树， m m