线段树合并学习笔记

有些时候，我们需要合并两棵动态开点线段树维护的信息，而一个个枚举插入又太慢了，这时就需要线段树合并的技巧。

假设现在要合并下图中蓝色的线段树和红色的线段树：

朴素的做法是一个一个叶节点插入，但是考虑同时在这两棵树上面 dfs：

两棵树的当前位置都有节点，所以继续往下递归：

两棵树的当前位置都有节点，继续往下递归：

发现蓝色线段树当前位置没有节点了，所以可以直接把红色线段树当前位置的节点拿来用，并回溯：

发现当前位置还没有递归处理完，往右递归：

发现红色线段树当前位置没有节点了，所以可以直接把蓝色线段树当前位置的节点拿来用，并回溯：

当前位置递归处理完了，新建一个节点来保存子树信息，并回溯：

发现当前位置还没有递归处理完，往右递归：

发现蓝色线段树当前位置没有节点了，所以可以直接把红色线段树当前位置的节点拿来用，并回溯：

当前位置递归处理完了，新建一个节点来保存子树信息，并回溯：

这样就完成了合并。

总结一下合并的规则：

• 同时在这两棵线段树上面 dfs；

• 若当前位置是叶节点，新建一个节点保存合并的信息，并回溯；

• 若两棵树的当前位置都有节点，继续往下递归；

• 若有一棵树当前位置没有节点了，直接把另一棵树当前位置的节点拿来用，并回溯；

• 当前位置递归处理完后，新建一个节点来保存子树信息，并回溯。

其中除了第二条，其它在图示里面都见过。第二条也很好理解，因为叶节点无需也没法继续递归下去。

将共有 $n$ 个叶子节点的任意多棵线段树以任意顺序合并的时间复杂度是 $O(n\log n)$ 的。证明如下：

不难发现，每次 dfs 合并两个节点可以看成丢掉一个节点，由于总共只有 $n\log n$ 个节点，所以时间复杂度就是 $O(n\log n)$ 的。

具体代码实现如下：

struct node
{
	int lson,rson;
	int val;
}tree[500005];

int cnt; // 节点数量（用于动态开点）

int meg(int x,int y)
{
	if(x==0||y==0) return x+y;
	if(tree[x].lson==0&&tree[x].rson==0)
	{
		int res=++cnt;
		tree[res]=tree[x];
		tree[res].val+=tree[y].val;
		return res;
	}
	else
	{
		int res=++cnt;
		tree[res].lson=meg(tree[x].lson,tree[y].lson);
		tree[res].rson=meg(tree[x].rson,tree[y].rson);
		upd(res);
		return res;
	}
}

有些时候空间卡得紧，我们在合并的时候可以不新建节点，代价是破坏某棵线段树的结构：

struct node
{
	int lson,rson;
	int val;
}tree[500005];

int cnt; // 节点数量（用于动态开点）

int meg(int x,int y)
{
	if(x==0||y==0) return x+y;
	if(tree[x].lson==0&&tree[x].rson==0)
	{
		tree[x].val+=tree[y].val;
		return x;
	}
	else
	{
		tree[x].lson=meg(tree[x].lson,tree[y].lson);
		tree[x].rson=meg(tree[x].rson,tree[y].rson);
		upd(x);
		return x;
	}
}

练习题目

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