当前位置：首页 > article >正文

线段树合并基础

article 2025/1/24 17:47:47

本人水平有限，这篇只讲线段树合并最基础的应用。

线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。由此，它多被用于维护树上或图上的信息，只要灵活选好每个点上线段树的下标含义，维护的信息，可以帮助你切掉许多困难的题。

首先我们难以把所有点全部建满线段树，所以线段树合并多用动态开点+权值线段树。
它合并的过程也十分简单：
设将 $y$ 子树合并到 $x$ 子树，则我们从各自的根节点开始递归合并；
若发现某树上对应的节点为空，则返回另一颗非空的节点。若递归到叶子结点，则把 $y$ 相应的信息返回给 $x$ 。

以洛谷模版题为例（链接）。
路径上修改某值，我们首先会想到树上差分，可是如何维护每个节点的颜色？这个时候就可以考虑线段树合并了，我们对每个节点都开一颗以颜色为下标的线段树，维护颜色出现的最大次数及出现最多的颜色，而这两个操作非常简便。处理询问就是若干次单点修改，最终统计答案合并的时候，将 $x$ 的所有儿子的线段树合并到它的线段树上，这道题就解决了。码量可能略长，但大部分全是模版。我就放上关键部分代码以供参考。

//...求LCA

//segment tree
void pushup(int u){
	if(sum[ls[u]]>=sum[rs[u]]) sum[u]=sum[ls[u]],typ[u]=typ[ls[u]];
	else sum[u]=sum[rs[u]],typ[u]=typ[rs[u]];
}
void modify(int &u,int l,int r,int p,int v){
	if(!u) u=++idx;
	if(l==r){sum[u]+=v,typ[u]=p;return;}
	int mid=(l+r)>>1;
	if(p<=mid) modify(ls[u],l,mid,p,v);
	else modify(rs[u],mid+1,r,p,v);
	pushup(u);
}
int merge(int x,int y,int l,int r){//线段树合并
	if(!x||!y) return x+y;
	if(l==r){sum[x]+=sum[y];return x;}
	int mid=(l+r)>>1;
	ls[x]=merge(ls[x],ls[y],l,mid);
	rs[x]=merge(rs[x],rs[y],mid+1,r);
	pushup(x);return x;
}
void merge_tree(int x,int father){
	for(int i=head[x];i;i=edge[i].nxt){
		int y=edge[i].to;
		if(y==father) continue;
		merge_tree(y,x);
		root[x]=merge(root[x],root[y],1,N);
	}
	ans[x]=sum[root[x]]?typ[root[x]]:0;
}

int main(){
	...
	
	while(m--){
		int x=read(),y=read(),z=read(),Lca=lca(x,y);
		modify(root[x],1,N,z,1),modify(root[y],1,N,z,1);
		modify(root[Lca],1,N,z,-1),modify(root[fa[Lca][0]],1,N,z,-1);
	}
	merge_tree(1,0);
	
	return 0;
}