1.线段树合并

P4556 雨天的尾巴

首先我们可以把链上操作转成树上差分。然后我们对每个节点开一棵权值线段树。朴素的树上差分都是开一个桶然后加和，但是这里开的是线段树。

所以就有了线段树合并。

在把 \(y\) 并到 \(x\) 的过程中，如果 \(x\) 本身没有一个 \(y\) 有的节点就可以直接把 \(y\) 的那个节点接上去节省时间。

就没了。

inline void merge(int x,int y){
	if(!sg[x].ls&&!sg[x].rs&&!sg[y].ls&&!sg[y].rs){//并到叶子节点了直接两个合起来
		sg[x].sm+=sg[y].sm;
		return;
	}
	if(sg[y].ls){//如果要并过来的没有左儿子就不用往左边合并了
		if(sg[x].ls)merge(sg[x].ls,sg[y].ls);
		else sg[x].ls=sg[y].ls;
	}
	if(sg[y].rs){
		if(sg[x].rs)merge(sg[x].rs,sg[y].rs);
		else sg[x].rs=sg[y].rs;
	}
	sg[x].sm=sg[sg[x].ls].sm+sg[sg[x].rs].sm;//更新
	return;
}

首先很容易看得出来单次合并的复杂度是 \(O(重合大小)\) 的。

那么对于 \(n\) 棵最开始只有一个元素的线段树，合并起来的复杂度是 \(O(n\log n)\)。这个很显然，因为就算所有元素都相等每次都跑满也只有 \(\log n\) 次。

注意线段树合并只能用于动态开点，因为普通线段树本来就是满的。

• 带转移的线段树合并（P5298 Minimax）

开个坑。

首先有朴素 dp：令 \(dp_{i,j}\) 表示节点 \(i\) 取到 \(j\) 的概率。假设这个值从左儿子传过来（右儿子同理），那么转移方程是 \(dp_{i,j}=dp_{ls,j}\times(p_i\times\sum_{k=1}^{j}dp_{rs,k}+(1-p_i)\times\sum_{k=j}^{n}dp_{rs,k})\)。

我们可以考虑用线段树合并。

2. 线段树分裂

P5494 【模板】线段树分裂

在分裂函数里面传当前节点，就是一边分裂一边建树。复杂度和区间查询一样。

inline void split(int ql,int qr,int &x,int &y,int l,int r){
	if(!x||qr<l||r<ql)return;
	if(ql<=l&&r<=qr){//就是要割的
		y=x;
		x=0;
		return;
	}
	if(!y)y=build();
	int mid=(l+r)>>1;
	if(ql<=mid)split(ql,qr,sg[x].ls,sg[y].ls,l,mid);
	if(qr>mid)split(ql,qr,sg[x].rs,sg[y].rs,mid+1,r);
	sg[x].sm=sg[sg[x].ls].sm+sg[sg[x].rs].sm;
	sg[y].sm=sg[sg[y].ls].sm+sg[sg[y].rs].sm;
	return;
}