线段树合并

简介

将多棵线段树的信息统一起来的高效算法称之为线段树合并。

通常合并顺序呈树状结构。

例题

P3224 [HNOI2012] 永无乡

假设所有点都在一个连通块里，那么我们只需要维护一个值域线段树并在上面二分即可。

但此时图不连通，我们该如何快速的统计信息呢？

对于连边，并查集可以胜任。

对于信息的合并，首先考虑新开一个寄存线段树。

显然是不行的，时空双爆。

由于一个线段树不一定像堆式建树一样全部建满的，我们可以考虑动态开点。

那么就很好办了，分别合并线段树的左右儿子，没右跑左，没左跑右，时间复杂度是线段树的深度 \(O(\log n)\)。

线段树代码：

namespace SGT {
	#define mid ((L + R) >> 1)
	#define son p, L, R
	#define lson ls[p], L, ((L + R) >> 1)
	#define rson rs[p], (((L + R) >> 1) + 1), R
	
	int tot, ls[N << 5], rs[N << 5];
	struct Node {
		int sum;
	} t[N << 5];
	
	inline void modify(int x, int &p, int L = 1, int R = n) {
		if(! p) p = ++ tot;
		
		t[p].sum = 1;
		
		if(L == R) return ;
		
		if(x <= mid) modify(x, lson);
		else modify(x, rson);
		
		return ;
	}
	
	inline int query(int k, int &p, int L = 1, int R = n) {
		if(L == R) return L;
		
		if(k <= t[ls[p]].sum) return query(k, lson);
		else return query(k - t[ls[p]].sum, rson);
	}
	
	inline int merge(int x, int y) {
		if(! x) return y;
		if(! y) return x;
		
		ls[x] = merge(ls[x], ls[y]);
		rs[x] = merge(rs[x], rs[y]);
		
		t[x].sum += t[y].sum;
		
		return x;
	}
	
	#undef mid
	#undef son
	#undef lson
	#undef rson
}