首页 > 其他分享 >浅谈一类动态开点线段树优化 - DEST树

浅谈一类动态开点线段树优化 - DEST树

时间:2024-10-11 21:00:07浏览次数:1  
标签:le 浅谈 val DEST Segt 线段 int null ri

前言

线段树,是一种优秀的数据结构,其应用极为广泛。其中,动态开点值域线段树,配合上线段树合并,甚至能替代或超越平衡树。但是,这种线段树的树高与值域相关,很容易产生四五倍常数。无论考虑时间或空间复杂度,这样的树都不算优。那么,我们是否能想办法优化它呢?

优化思想

正如上文所述,普通线段树(本文中特指动态开点线段树,下同)的树高和值域相关。叶结点稀疏时,树上会存在若干孤链,如下图:

这些链唯一的作用是,连接根与叶结点。显然,这其中有巨大的优化空间。我们的思想很简单,压缩树高!准确来说,我们把任意时刻的线段树,都视为压缩后的树,并在此基础上做“扩展”。每次修改只新建少数必要的结点,从而间接起到压缩树结构的效果。

另外,为防止毒瘤数据卡结构,还需要一个“收缩”操作,动态删除无意义的叶结点,微调整棵树的结构。(虽然整棵树的结构问题不在这儿)

实现方法

首先,我们将下文中的普通线段树称为原树,将与之对应合法的、压缩后的树称为压缩树。

压缩了树高,自然丢失了区间左右端点信息。所以,我们需要在每个结点上存储,其对应的叶结点区间 $[s, t]$。为了实现方便,我们规定(很重要!):

  • 压缩树结点上任意的 $[s, t]$ 区间,都必须对应原树上的某一 $[l, r]$ 区间。
  • 原树上一个点,经压缩后,只能挂在其若干级祖先的位置上。不能挂在兄弟或儿子,或其他地方。(当然,也可以直接删去)

也就是说,压缩后树上的点,必须和原树一一对应。即,压缩树结点集合到原树结点集合的映射,必须是一个单射。并且,压缩树上的任意一点,只可能是其子树内的结点。下图是一个原树与压缩树对应的例子:

不难发现,压缩树确实比原树矮了不少。要实现这样的压缩,大力分类讨论是少不了的。在这里,我提供一种分类讨论的顺序:先空,再包含,最后相离。以这个顺序讨论,可以最大程度地简化代码。接下来我会以一棵,单点修改区间查询线段树为例,从代码层面剖析整棵树。

结点信息

如上文所述,树上结点的结构体是这样的:

struct Segt {
	int val; // 维护的区间和信息
	int s, t; // 代表 [s, t] 区间
	Segt *le, *ri; // 指向左右子结点的指针
	Segt(); Segt(int val, int s, int t, Segt* le, Segt* ri);
} null_(0, 0, 0, &null_, &null_), *null = &null_;
// 补全构造函数
Segt::Segt(): val(0), s(0), t(0), le(null), ri(null) {}
Segt::Segt(int val, int s, int t, Segt* le, Segt* ri): val(val), s(s), t(t), le(le), ri(ri) {}

需要动态开点时,本人喜欢用指针树。需要注意,最好新建一个点代表空结点,不要用 nullptr,否则很容易访问到空地址,导致 RE。

辅助函数

在介绍修改、查询、合并操作前,我们需要先实现三个辅助函数:

pushup

void pushup(Segt* u) {
	if (u->s == u->t) return; // 跳过叶子结点
	u->val = u->le->val + u->ri->val;
}

因为线段树是 Leafy Tree,所以最好别对叶子结点做 pushup。可以通过区间端点信息,辨认叶子结点。

adjust

bool adjust(int x, int y, int &l, int &r) {
	int mid = (l + r) >> 1;
	if (x <= mid && y <= mid) return r = mid, true;
	if (mid < x && mid < y) return l = mid + 1, true;
	return false;
}

在代码中使用 while(adjust(x, y, l, r));,可以快速找到一组 $[l, r]$,使得 $x \in [l, mid], y \in [mid + 1, r]$,其中 $mid = \lfloor \frac{l + r}{2} \rfloor$。也就实现了在压缩树上,遍历原树一些不必要的结点。

maintain

void maintain(Segt*& u) {
	if (u->s == u->t) {
		if (u->val == null->val) u = null;
	}
	else if (u->le == null) u = u->ri;
	else if (u->ri == null) u = u->le;
}

这个函数实现了收缩操作。但是,不收缩的压缩树,在时间上也足以应对常见的题目(可用可不用)。因此,收缩操作的优化,更多体现在空间复杂度上。

现有两种情况需要收缩:

  • (叶结点)点权为 0,对答案没有贡献。
  • (非叶结点)位于一条链上,即只有一个儿子。

另外,如果当前点非叶结点,又没有儿子,应当直接删去。不过上述代码兼容了这种情况,在实现上可以忽略。

单点修改

void update(Segt*& u, int l, int r, int pos, int val) {
	// 当前结点为空
	if (u == null) {
		u = node(pos, pos, val); // 直接新建一个叶结点,返回
		return;
	}
	// 当前结点包含待修改位置
	if (u->s <= pos && pos <= u->t) {
		// 如果是叶子
		if (u->s == u->t) {
			u->val += val;
			// maintain(u);
			return;
		}
		// 如果不是叶子,正常递归
		int mid = (u->s + u->t) >> 1;
		if (pos <= mid) update(u->le, u->s, mid, pos, val);
		else update(u->ri, mid + 1, u->t, pos, val);
	}
	// 当前结点不包含待修改位置
	else {
		while (adjust(u->s, pos, l, r)); // 在原树上找到一个合适的点 [l, r]
		Segt *v = node(pos, pos, val);
		// 此时,u v 必然在 mid = (l + r) / 2 的两边,挂上去即可
		if (v->s < u->s) swap(u, v);
		u = node(l, r, u, v);
	} 
	pushup(u);
	// maintain(u);
}

我们以 空、包含、相离 的顺序讨论,不难发现,“包含”部分的写法和普通线段树几乎一样,只是用 u->s, u->t 代替了平时的 l, r。你可以先这样理解:$[s, t]$ 才是真正的区间范围,$[l, r]$ 只是用来调整压缩树结构的。我们很贪心,只要满足条件,就新建结点并立刻返回,实在不行再递归。

区间查询

int query(Segt* u, int L, int R) {
	if (u == null) return 0;
	if (L <= u->s && u->t <= R) return u->val;
	int mid = (u->s + u->t) >> 1;
	if (R <= mid) return query(u->le, L, R);
	if (mid < L) return query(u->ri, L, R);
	return query(u->le, L, R) + query(u->ri, L, R);
}

没什么好说的,就是很普通的区间查询。特殊的是,我们已经在结点上存储了,区间左右端点的信息,因此不再需要传入 $[l, r]$ 作为函数参数。

线段树合并

Segt* merge(Segt* u, Segt* v, int l, int r) {
	if (u == null) return v;
	if (v == null) return u;
	// 保证 u 的区间长度比 v 大
	if (u->t - u->s < v->t - v->s) swap(u, v);
	// u = copy(u); 可持久化合并,在这里复制一份 u 即可
	if (u->s <= v->s && v->t <= u->t) { // 如果包含
		if (u->s == u->t) { // 叶子合并
			u->val += v->val;
			// maintain(u);
			return u;
		}
		// 非叶子合并,要判断 u 和 v 的区间关系
		int mid = (u->s + u->t) >> 1;
		// 如果 v 在 u 的半边,用 u 的一半与 v 合并,否则正常合并
		if (v->s <= mid) u->le = merge(u->le, v->t <= mid ? v : v->le, u->s, mid);
		if (mid < v->t) u->ri = merge(u->ri, mid < v->s ? v : v->ri, mid + 1, u->t);
	} else {
		// 不包含,处理方法与修改操作相同
		while (adjust(u->s, v->s, l, r));
		if (v->s < u->s) swap(u, v);
		u = node(l, r, u, v);
	}
	pushup(u);
	// maintain(u);
	return u;
}

还是 空、包含、相离 的顺序。需要注意,“包含”递归时需要特殊判断 u 和 v 的区间关系,“相离”的处理逻辑与修改操作很像,也是,先调整 $[l, r]$ 位置,再新建一个点返回。

线段树分裂

我不会,没写。 应该可以直接分裂,回溯时用 maintain 收缩一下就好了。

完整代码

整棵树写起来并不长,分类讨论也很好记,没有很麻烦。上文中写得长,是因为有注释,稍微压行后就很短了。(合理压行)

另外,线段树如何动态开点,就不用多说了吧?看代码应该能懂。

// 结构体
struct Segt {
	int val, s, t;
	Segt *le, *ri;
	Segt(); Segt(int val, int s, int t, Segt* le, Segt* ri);
} null_(0, 0, 0, &null_, &null_), *null = &null_;
Segt::Segt(): val(0), s(0), t(0), le(null), ri(null) {}
Segt::Segt(int val, int s, int t, Segt* le, Segt* ri): val(val), s(s), t(t), le(le), ri(ri) {}

void pushup(Segt* u) {
	if (u->s == u->t) return;
	u->val = u->le->val + u->ri->val;
}

// 创建结点
Segt pool[N_ * 10]; int psz;
Segt* node() { return pool + (++psz); }
Segt* node(int val, int s, int t, Segt* le, Segt* ri) { Segt *u = node(); *u = Segt(val, s, t, le, ri); return u; }
Segt* node(int s, int t) { return node(0, s, t, null, null); }
Segt* node(int s, int t, int val) { return node(val, s, t, null, null); }
Segt* node(int s, int t, Segt* le, Segt* ri) { Segt *u = node(0, s, t, le, ri); return pushup(u), u; }

// 调整 [l, r]
bool adjust(int x, int y, int &l, int &r) {
	int mid = (l + r) >> 1;
	if (x <= mid && y <= mid) return r = mid, true;
	if (mid < x && mid < y) return l = mid + 1, true;
	return false;
}

// 收缩
void maintain(Segt*& u) {
	if (u->s == u->t) { if (u->val == null->val) u = null; }
	else if (u->le == null) u = u->ri;
	else if (u->ri == null) u = u->le;
}

// 单点修改
void update(Segt*& u, int l, int r, int pos, int val) {
	if (u == null) return u = node(pos, pos, val), void();
	if (u->s <= pos && pos <= u->t) {
		if (u->s == u->t) return u->val += val, maintain(u), void();
		int mid = (u->s + u->t) >> 1;
		if (pos <= mid) update(u->le, u->s, mid, pos, val);
		else update(u->ri, mid + 1, u->t, pos, val);
	} else {
		while (adjust(u->s, pos, l, r));
		Segt *v = node(pos, pos, val);
		if (v->s < u->s) swap(u, v);
		u = node(l, r, u, v);
	} pushup(u), maintain(u);
}

// 区间查询
int query(Segt* u, int L, int R) {
	if (u == null) return 0;
	if (L <= u->s && u->t <= R) return u->val;
	int mid = (u->s + u->t) >> 1;
	if (R <= mid) return query(u->le, L, R);
	if (mid < L) return query(u->ri, L, R);
	return query(u->le, L, R) + query(u->ri, L, R);
}

// 线段树合并
Segt* merge(Segt* u, Segt* v, int l, int r) {
	if (u == null) return v;
	if (v == null) return u;
	if (u->t - u->s < v->t - v->s) swap(u, v);
	if (u->s <= v->s && v->t <= u->t) {
		if (u->s == u->t) return u->val += v->val, maintain(u), u;
		int mid = (u->s + u->t) >> 1;
		if (v->s <= mid) u->le = merge(u->le, v->t <= mid ? v : v->le, u->s, mid);
		if (mid < v->t) u->ri = merge(u->ri, mid < v->s ? v : v->ri, mid + 1, u->t);
	} else {
		while (adjust(u->s, v->s, l, r));
		if (v->s < u->s) swap(u, v);
		u = node(l, r, u, v);
	} return pushup(u), maintain(u), u;
}

性能分析

假设存在一个问题,共有 $M$ 次操作,线段树的下标范围是 $[1, N]$。

时间复杂度

update / query

一般 $O(\log M)$;最坏 $O(\log N)$;

这里的最坏情况中,所有下标为 $2 ^ n + 1$ 的点都在线段树中,这足以将整棵树卡成一条“有用的链”。

实际的复杂度取决于树高,以及数据的分布。

merge

我不会分析。大概可以近似成两棵普通线段树合并。复杂度应该与树高相关。

空间复杂度

update / merge

严格 $O(M)$。前者每次调用最多新建两个结点,后者最多一个。

常数

显然比普通树更小。直接看对比图(线段树合并模板):

压缩树

原树

结语

实际上,如果你的算法功底足够深厚,就会发现,压缩树其实就是原树的,一棵不严格的虚树。只不过,用虚树的方法,维护严格的虚树过于麻烦,使用扩展树高的技巧,实现起来会简单一些。如果你对严格的虚树优化感兴趣,不妨自行阅读这篇文章:浅谈维护叶子节点及其所构成的虚树的一类线段树

综上,压缩过树高的线段树,相比一般的动态开点线段树,无论在时间或空间,复杂度或常数方面,都更加优秀。并且,相比于严格的虚树实现,“扩展树”的实现显然码量更小,更容易记忆理解。我个人认为,这是一种十分普信的数据结构(优化),并且完全可以应用于实战中。

此外,本人经过几天搜索,未找到类似的文章。故单方面把这种优化后的线段树,命名为“Dest 树”(Dynamic Extension Segment Tree)。若已存在其它名字,请诸位及时告知我,以撤销本命名。

后记

分析时间复杂度时,才发现会被卡时间(空间不会)。难受了。但是,被卡总比不优化好,也算是咱研究了好几天的成果啊。最终决定,还是要写本文,将其公之于众。

标签:le,浅谈,val,DEST,Segt,线段,int,null,ri
From: https://www.cnblogs.com/lateworker/p/18459326

相关文章

  • 可持久化线段树
    可持久化线段树P3919【模板】可持久化线段树1(可持久化数组)维护一个长度为\(N\)的数组,支持如下几种操作在某个历史版本上修改某一个位置上的值访问某个历史版本上的某一位置的值此外,每进行一次操作(对于操作2,即为生成一个完全一样的版本,不作任何改动),就会生成一个新......
  • 浅谈云原生--微服务、CICD、Serverless、服务网格
    往期推荐 浅学React和JSX-CSDN博客一文搞懂大数据流式计算引擎Flink【万字详解,史上最全】-CSDN博客一文入门大数据准流式计算引擎Spark【万字详解,全网最新】_大数据spark-CSDN博客目录1.云原生概念和特点2.常见云模式3.云对外提供服务的架构模式3.1IaaS(Infrast......
  • 李超线段树
    1问题李超线段树是线段树的一种变种,主要用于维护二维平面上的直线信息以及查询操作。它的应用范围很广,只要式子的形式能转化为一次函数就可以考虑使用李超线段树进行求解/优化。具体的,李超线段树支持下面两种操作:动态在平面中插入一条线段/直线。在平面上询问与一条直线......
  • Mysql锁机制浅谈一
    mysql是如何加锁的?加锁默认是加临键锁,有特殊情况会优化为其他锁索引上的等值查询:唯一索引,给不存在的记录加锁时,优化为间隙锁普通索引,向右遍历至最后一个不满足查询条件的值时吗退化为间隙锁索引上的范围查询:唯一索引:访问到不满足条件的第一个值为止主键索引ps:如果是......
  • 浅谈SG函数
    文章目录写在前面公平游戏写在前面听说CSDN给米就来了,不过作为一个品质优良的程序员来说,无私奉献是我应该做的,所以博主写的文章基本上不花钱,都是为了以后某天忘记了,自己能看懂才写的。so,我会写的很啰嗦,直到保证忘记的我能够看懂。对于读者嘛,能看就看吧,我就不管了。......
  • 李超线段树
    最经典应用就是维护一个二维平面直角坐标系,支持动态插入线段(理解为有值域的一次函数\(y=kx+b\)),询问已插入线段与直线\(x=x_0\)交点的纵坐标最值。即当\(x=x_0\),求\(max\)或\(min\){\(k_ix+b_i\)}对于普通求法的\(O(n)\)遍历,如何优化时间复杂度呢?其实就是找一种方......
  • B. 线段取交
    题目下载链接算法可以发现是求逆序对时间复杂度限制在\(O(n\logn)\)树状数组记录每一个值的多少转化为求前缀和#include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;inttree[500010],ranks[500010],n;longlongans;structpoint{......
  • 浅谈 $prufer$ 序列
    \(purfer\)序列,是为了证明\(cayley\)定理。具体来说,是将一个树映射到一个数组上,在数组上可以使得很多东西更加清晰的展示。构造\(prufer\)序列\(prufer\)是将一个大小为\(n\)的树映射到长度\(n-2\)的序列上。从一个无根树开始,我们将树入度为\(1\)的点找出来,及叶子......
  • 浅谈IT行业的未来发展趋势
    浅谈IT行业的未来发展趋势随着科技的不断进步,IT行业的发展进入了一个崭新的阶段。今天,我们就来浅谈一下IT行业的未来发展趋势,探讨那些可能会改变我们生活的技术。1.人工智能与自动化人工智能(AI)和自动化技术已经在各个领域崭露头角。未来,随着AI算法的进一步优化和硬件性......
  • 2024.10.1 总结(集训;数据结构 主要是线段树)
    XK又来给我们讲课了。开心!1.Baka'sTrick两种理解:双栈模拟队列。[找到若干个划分点,使得每个区间包含恰好一个划分点。维护划分点到划分点段的前缀、后缀信息。在在线的实现中,在队列中维护仅仅一个划分点,维护它到前面每个点和它到后面每个点的信息。当这个划分点出队时,把队......