• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【笔记】线段树合并

开发技术 开发技术 4小时前 1次浏览

有了动态开点线段树,就有了这种东西

你在树上跑,是不是经常很想用权值线段树维护一些东西
然后马上觉得不行,你从这个子树下去对线段树一通操作,那你等会去另一个子树时被影响到了怎么办
然后你又想,如果每个子树(的根节点)都有一个线段树,然后合并起来不好吗
那这不是在扯淡吗,线段树开多大,合并的话还得全走一遍那怎么过的去
但是,
如果是动态开点的线段树的话
如果只进行点修改的话
如果修改规模等同于 N 的话
那就可以了
为什么?
首先是点修改:

void update(int &x, int l, int r, int p) {
	if (!x) x = ++tot;
	if (l==r) { sum[x]++; }
	else {
		int mid = (l + r) >> 1;
		if (mid>=p) update(lson, l, mid, p);
		if (mid< p) update(rson, mid+1, r, p);
		pushup(x);
	}
}

(这个写法比我原来的更好呢, &x 这个地方)
一次点修改是 log 的复杂度, k 个节点最坏就是 klogk
对于合并,我们把子节点 v 的线段树合并到父节点 u 上去:

ST.merge(rt[u], rt[v], 1, N);
int merge(int x, int y, int l, int r) {
	if (!x) return y;
	if (!y) return x;
	if (l==r) { sum[x] += sum[y]; return x; }
	else {
		int mid = (l + r) >> 1;
		ls[x] = merge(ls[x], ls[y], l, mid);
		rs[x] = merge(rs[x], rs[y], mid+1, r);
		pushup(x);
		return x;
	}
}

合并过程中,如果其中一个的子节点是 null ,那就直接连到另一个的儿子上去
如果不是,那么合二为一(要求维护信息可以合并),意味着我们删掉了一个节点,然后继续递归子区间做下去
那么最后的时空复杂度呢?
点修改次数 M , M 与 N 相当,那么空间复杂度最坏是 NlogN ,这里注意一下修改带的常数,比如树上差分什么的
考虑合并带来的复杂度,对于每个节点,它被“删”了就再也不会出现了;如果没有“删”,也就是出现了null,那就停住不走,所以说,我们可以大致把不删看成是一系列“删”的尾声,这是个常数;而“删”显然就是 NlogN
所以复杂度是优秀的 NlogN

一般的,我们都用值域线段树来合并,维护东西也比较有用

luoguP4556 【模板】线段树合并 :就是板子题

struct segmentTree {
	#define lson ls[x]
	#define rson rs[x]
	int tot, maxv[MAXN<<2], val[MAXN<<2], ls[MAXN<<2], rs[MAXN<<2];
	segmentTree() {
		memset(maxv, 0, sizeof(maxv));
		memset(val, 0, sizeof(val));
	}
	void pushup(int x) {
		if (maxv[lson]> maxv[rson]) {
			maxv[x] = maxv[lson], val[x] = val[lson];
		}
		if (maxv[lson]< maxv[rson]) {
			maxv[x] = maxv[rson], val[x] = val[rson];
		}
		if (maxv[lson]==maxv[rson]) {
			maxv[x] = maxv[lson], val[x] = val[lson];
		}
	}
	void update(int &x, int l, int r, int p, int v) {
		if (!x) x = ++tot;
		if (l==r) {
			maxv[x] += v, val[x] = l;
		} else {
			int mid = (l + r) >> 1;
			if (mid>=p) update(lson, l, mid, p, v);
			if (mid< p) update(rson, mid+1, r, p, v);
			pushup(x);
		}
	}
	int merge(int x, int y, int l, int r) {
		if (!x) return y;
		if (!y) return x;
		if (l==r) {
			maxv[x] += maxv[y], val[x] = l;
			return x;
		} else {
			int mid = (l + r) >> 1;
			ls[x] = merge(ls[x], ls[y], l, mid);
			rs[x] = merge(rs[x], rs[y], mid+1, r); // r not y! fuck!
			pushup(x); // wtf
			return x;
		}
	}
	void debug(int x, int l, int r) {
		printf("  (%d, %d), maxv=%d, val=%dn", l, r, maxv[x], val[x]);
		if (l==r) return;
		else {
			int mid = (l + r) >> 1;
			if (lson) debug(lson, l, mid);
			if (rson) debug(rson, mid+1, r);
		}
	}
} ST;

另外我们一般需要用一个 rt[] 数组来记录树上每个节点自己的线段树的根节点是哪个,一般来说我们可以直接钦定:

for (int i=1; i<=N; i++) rt[i] = i; ST.tot = N;

你要一边遍历树一边钦定也行

例题
[POI2011]ROT-Tree Rotations :维护子树逆序对数,你要是知道线段树合并,逆序对怎么求自然就知道了


程序员灯塔
转载请注明原文链接:【笔记】线段树合并
喜欢 (0)