菜王的 blog

线段树合并

顾名思义，线段树合并是把两棵线段树合并到一起的算法。

假如有两棵动态开点的线段树，一棵根节点为 $u1$，另一棵根节点为 $u2$。

$\operatorname{Merge}(u1, u2)$ 函数可以将 $u2$ 合并到 $u1$ 上并返回新树的根，流程如下：

1. 如果 $u1$ 和 $u2$ 至少有一个为空，返回另一个。
2. 如果到了叶子节点，直接合并。
3. 令 $ls_{u1} = \operatorname{Merge}(ls_{u1}, ls_{u2})$。
4. 令 $rs_{u1} = \operatorname{Merge}(rs_{u1}, rs_{u2})$。
5. 返回 $u1$。

由于每一个节点至多会被访问一次，所以时间复杂度不会超过两个线段树重叠的部分。

代码实现：

int Merge(int u1, int u2, int l, int r){
	if (!u1) return u2;
	if (!u2) return u1;
	if (l == r){tr[u1].cnt += tr[u2].cnt;return u1;}
	int mid = l + r >> 1;
	tr[u1].ls = Merge(tr[u1].ls, tr[u2].ls, l, mid);
	tr[u1].rs = Merge(tr[u1].rs, tr[u2].rs, mid + 1, r);
	pushup(u1);
	return u1;
}

例题

【模板】线段树合并

[HNOI2009] 梦幻布丁