线段树合并

闲话/前言

---

前置知识

• 权值线段树

• 动态开点线段树

• 普通线段树合并

---

动态开点线段树

动态开点用于空间超大且很多无用的节点的类型的线段树，一般用于优化权值线段树。

对于每一个线段树上的节点 $p$，记录下其左儿子 $ls$ 和右儿子 $rs$ 的编号。

在每次遍历树时，如果需要再使用一个节点：

• 1.该节点不存在，新建节点，同时记录儿子；

• 2.若该店存在，直接深入遍历即可。

这里我们可以开一个数组 $r{t}_i$ 记录 $i$ 元素在动态开点线段树中的编号；

每次使用节点时，再调用 $i$ 元素的 $rt$ 即可...

---

普通线段树合并

顾名思义，线段树合并就是将多棵线段树的信息合并起来，用一棵线段树来保存。

对于两棵线段树 $A$ 和 $B$ 的合并过程：

① 若对于一个位置 $p$，$A$ 有，$B$ 没有，新的线段树 $p$ 位置赋成 $A$，返回 $A$；反过来同理，$B$ 有，$A$ 没有，赋成 $B$，返回 $B$；

② 若合并到叶子结点，按照所需合并 $A$ 和 $B$，把新线段树上的 $p$ 位置赋成 $A$，返回 $A$；

③ 重复递归位置 $p$ 的左子树和右子树，并更新并返回当前节点 $p$。

这边建议尝试通过程序实现来理解。

其比较普遍有两种方式实现：

• 1.新建一棵线段树来存储；

• 2.将一棵线段树直接合并到另一棵上。

这两种就相当于 $c=a+b$ 和 $a+=b$，第二种方法则更节省空间，缺点是丢失了一棵线段树的原始信息。

线段树合并通常基于动态开点线段树和权值线段树来实现。

使用线段树合并的前提最好是合并的两棵线段树维护同样的参数，例如都维护的是每个数出现的个数。

无特殊情况，较倾向于第二种方法实现：

inline int merge_(int a,int b,int l,int r) {
	if(!a) return b;
	if(!b) return a;
	if(l==r) {
    /* 合并所需的参数操作 */
		return a;
	}
	int mid=(l+r)>>1;
	tree[a].ls=merge_(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge_(tree[a].rs,tree[b].rs,mid+1,r);
	push_up(a);
	return a;
}

关于时间和空间复杂度

【时间复杂度】

• 你别管他怎么证明的，就是启发式合并的时间复杂度，$O(nlogn)$ ，包的。 --ljs

本蒟蒻较弱，以后再回来证吧...

【空间复杂度】

一般考虑动态开点一共开了多少个点，假设每次动态开点都能新建线段树上一条长度为 $logn$ 的链，有 $m$ 次，则空间大小就为 $mlogn$。

---

[Vani有约会] 雨天的尾巴 /【模板】线段树合并

简要题意

给定有 $n$ 个节点的树形结构图，有 $m$ 次操作，每次操作将 $x$ 到 $y$ 的简单路径上所有节点都加上 $1$ 个颜色 $c$，求问每个点上出现次数最大的颜色是哪个。

闲话

• 遇到树上简单路径首先要思考树上差分和树链剖分，次考虑树上 dp 或换根 dp。

Solution

说实话有链操作的题就想用树剖做...

操作部分明显可以用树上差分搞，先考虑暴力在每个点上都建一棵权值线段树维护每种颜色出现的次数；

执行操作时，对于每一组 $u$ 和 $v$，设其的 LCA 为 $x$，那么可以分别在 $u$ 和 $v$ 处将 $c$ 加上 $1$，在 $x$ 和 $f{a}_x$ 处将 $c$ 加上 $-1$。

发现线段树上有很多没使用的点，可以用动态开点优化。

最后对于每个点 $u$ 颜色 $col$ 出现的个数就为所有子树 $v_i$ 中的 $col$ 的个数之和（差分思想），此处就要使用线段树合并；

即在统计点上出现颜色的个数时遍历树，从下到上，将 $u$ 与其儿子 $v_i$ 的权值线段树合并，并记录答案即可。

注意：对于每个点我们要开一个 $r{t}_i$ 表示第 $i$ 个点在动态开店中的编号，不能在线段树中开！！会搞混乱的，请自己理解一下，嘻嘻...

理解了这一题的整个程序思路就已经入门了（自我感觉）。

Code【模板】

模板题就放一下代码吧...

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,rt[N],id;
struct Node {
	int to,nxt;
	Node() {
		to=nxt=0;
	}
	Node(int a,int b) {
		to=a,nxt=b;
	}
} adj[N<<1];
struct Tree {
	int ls,rs;
	int cnt,col;
} tree[4*22*N];
int head[N],idx;
int dep[N],f[N][22],ans[N];
inline void add(int x,int y) {
	adj[++idx]=Node(y,head[x]);
	head[x]=idx;
	return ;
}
inline void push_up(int p) {
	if(tree[tree[p].ls].cnt>=tree[tree[p].rs].cnt) {
		tree[p].cnt=tree[tree[p].ls].cnt;
		tree[p].col=tree[tree[p].ls].col;
	} else {
		tree[p].cnt=tree[tree[p].rs].cnt;
		tree[p].col=tree[tree[p].rs].col;
	}
	return ;
}
inline void dfs1(int u,int fa) {
	dep[u]=dep[fa]+1,f[u][0]=fa;
	for(int i=1;i<=20;i++)
		f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=adj[i].nxt) {
		int v=adj[i].to;
		if(v==fa)
			continue;
		dfs1(v,u);
	}
	return ;
}
inline int lca(int x,int y) {
	if(dep[x]<dep[y])
		swap(x,y);
	for(int i=20;i>=0;i--) {
		if(dep[f[x][i]]>=dep[y])
			x=f[x][i];
	}
	if(x==y)
		return x;
	for(int i=20;i>=0;i--) {
		if(f[x][i]!=f[y][i]) {
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
inline void update(int &p,int l,int r,int k,int v) {
	if(!p) p=++id;
	if(l==r) {
		tree[p].cnt+=v;
		tree[p].col=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid)
		update(tree[p].ls,l,mid,k,v);
	else update(tree[p].rs,mid+1,r,k,v);
	push_up(p);
	return ;
} 
inline int merge_(int a,int b,int l,int r) {
	if(!a) return b;
	if(!b) return a;
	if(l==r) {
		tree[a].cnt=tree[a].cnt+tree[b].cnt;
		return a;
	}
	int mid=(l+r)>>1;
	tree[a].ls=merge_(tree[a].ls,tree[b].ls,l,mid);
	tree[a].rs=merge_(tree[a].rs,tree[b].rs,mid+1,r);
	push_up(a);
	return a;
}
inline void dfs2(int u,int fa) {
	for(int i=head[u];i;i=adj[i].nxt) {
		int v=adj[i].to;
		if(v==fa)
			continue;
		dfs2(v,u);
		rt[u]=merge_(rt[u],rt[v],1,N-1);
	}
	if(tree[rt[u]].cnt)
		ans[u]=tree[rt[u]].col;
	return ;
}
signed main() {
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<n;i++) {
		int x,y;
		scanf("%lld%lld",&x,&y);
		add(x,y),add(y,x);
	}
	dfs1(1,0);
	for(int i=1;i<=m;i++) {
		int u,v,c;
		scanf("%lld%lld%lld",&u,&v,&c);
		int x=lca(u,v);
		update(rt[u],1,N-1,c,1);
		update(rt[v],1,N-1,c,1);
		update(rt[x],1,N-1,c,-1);
		update(rt[f[x][0]],1,N-1,c,-1);
	}
	dfs2(1,0);
	for(int i=1;i<=n;i++)
		printf("%lld\n",ans[i]);
	return 0;
}

---

[HNOI2012] 永无乡

前言

这题的 $p$ 是全排列，还是很好心的嘛...

简要题意

一开始给定一个 $n$ 个点 $m$ 条边的图和每个点的价值 $p_i$。

$q$ 次询问，两个操作，一个是在 $x$ 和 $y$ 间连一条边，另一个查找所有与 $x$ 连通的点中第 $y$ 小的点。

Solution

一眼就要想到用并查集连通联通分量的点，再建一棵权值线段树维护当前的连通分量中每个价值是否存在 $cnt$；

由于所有点的价值是全排列，很人性化，所以我们可以用 $r{d}_i$ 表示价值为 $i$ 的点，查询到最后时，只用返回 $r{d}_l$ 即可，可以像这样：

inline int query(int p,int l,int r,int k) {
	if(l==r) return rd[l];
	int mid=(l+r)>>1;
	if(tree[tree[p].ls].cnt>=k)
		return query(tree[p].ls,l,mid,k);
	else return query(tree[p].rs,mid+1,r,k-tree[tree[p].ls].cnt);
}

---

[ABC372E] K-th Largest Connected Components

Solution

这一题和上一题差不多，设该点所在连通块个数为 $num$，则查找其中的第 $k$ 大值，相当于查找第 $num-k+1$ 小的值。

---

[ABC365G] AtCoder Office

闲话

和前面的单点修个，这个是区间线段树合并，且空间复杂度分析也不一样...

Solution

---

文章部分用语来源&鸣谢

线段树合并

【学习笔记】线段树合并

---

线段树分裂

前置知识

• 线段树合并

待更新...

---