线段树合并学习笔记

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

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

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

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

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

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

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

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

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

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

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

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

这样就完成了合并。

总结一下合并的规则:

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

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

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

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

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

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

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


不难发现,每次 dfs 合并两个节点可以看成丢掉一个节点,由于总共只有 nlognn\log n 个节点,所以时间复杂度就是 O(nlogn)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;
	}
}

练习题目