30分钟~,搞定线段树结构!!

注明:目前使用线段树的次数不多,如果细节部分有微小错误,还请在评论区指证,谢谢!

基本认识

线段树是一种常用的数据结构,对于研究算法的acmer来说,更是必不可少。
但是主流的一些教材上,却往往对其避而不谈,例如《算法导论》、《数据结构》等等。
原因是,线段树相对其他常用数据结构来说,使用频率较低,而且难度相对较大。

但是其实一旦理解好了其内部原理,线段树的实现就很简单了。
线段树和区间树有着许多的相似之处,因此了解区间树有利于更好地学习线段树(没有学过也不要紧),线段树就像是区间树的升级版,先难后易也可。

在学习线段树之前,我们首先要明白,为什么线段树在区间数据的修改上有着很大的优势。

例如,给你一个长度为10000的数组,让你进行如下操作,每一次修改一个区间的值,让里面的数字同时加上或者减去一个值,求最后这10000个数的和。

如果用暴力解决,循环修改区间里的数字,当操作的次数增多时,非常容易超时。
但是改用线段树,就能大大减小时间复杂度。

原因是因为线段树不会直接一个个修改区间的值,而是利用一个lazy标记,代替一个区间所需要修改的值,从而减小不必要的复杂度。

当然,可能大家也有过这样的思路,既然是对区间进行操作,那为什么不直接合并区间,最后求和呢?
我自己也试过这样的方法,但是实际执行起来会发现一个问题,为了避免区间的重合,你每一次合并区间,都要查找区间之间是否有重合的部分,造成的结果就是时间复杂度会达到o(n*n).
一旦面临n过大的题目,不可避免的会超时。

线段树实现

前言说完,现在我们来讲讲线段树实现。
看一个结构图(因为懒得自己画就拿了个别人的……):
30分钟~,搞定线段树结构!!
线段树的源节点是节点1,这一点必须注意,因为数组开始是0,建树的时候必须小心。

使用线段树之前,肯定得有存储结构。
线段树一般存在一维数组中,为了避免越界问题,空间复杂度要开到4n,在下面代码我使用a代表线段树的数组。
同理lazy标记也需要一个4n的数组。

下面的例子以维护区间和为例,但是需要知道的是,线段树不只可以维护区间和,也可以维护例如区间最大值、区间乘积之类的信息。

线段树操作可以分为五个部分,:
buildtree(如果有初始值)
mark(标记一个区间的lazy)
pushdown(向下标记,也就是向左右子树标记)
update(更新一个区间,也就是修改)
query(获取一个区间的求和值)。

总结起来,线段树的实现就是遇到一个区间时,能整体update操作就不少量操作,实在不行就只能pushdown缩小区间,再update操作。做完了就query获取成果。

首先,对于有初始值的题目,我们需要建树,建树的过程中因为涉及到线段树变换,所以需要维护区间和。

补充:线段树是树状结构,poi<<1 表示当前位置的左子树,poi<<1|1表示当前位置的右子树

void buildtree(int* t,int poi,int l,int r)//注意数组要足够长,不要越界
{
	if (l == r)
	{
		a[poi] = t[l];
		return;
	}
	int mid = l + r >> 1;
	buildtree(t, poi << 1, l, mid);
	buildtree(t, poi << 1 | 1, mid+1, r);
	a[poi] = a[poi << 1] + a[poi<< 1 | 1];//建树也不要忘记维护区间和
}

然后是mark操作,将lazy标记传下去,这一步很简单,同样需要维护区间和。

void mark(int poi, int l, int r, int k)
{
	a[poi] += (r - l + 1) * k;//维护
	lazy[poi] += k;
}

接着是pushdown操作,目的是将当前位置的lazy标记清空并且向子树传,依赖于mark实现。

void pushdown(int poi,int l,int r)
{
	int mid = l + r >> 1;
	mark(poi << 1, l, mid,lazy[poi]);
	mark((poi << 1)+1, mid+1, r, lazy[poi]);
	lazy[poi] = 0;
}

然后是update操作,对区间的值进行更新,要注意细节,维护区间和。

void update(int poi, int l, int r,int x,int y,int v)
{
	if (x <=l && y >=r)//如果当前区间在想要修改的范围内,就直接修改
	{
		mark(poi, l, r, v);
		return;
	}
//不在范围内时,需要对以中间为界两边进行查找
		int mid = l + r >> 1;

		if (lazy[poi] != 0)//不为0才pushdown,为0 的话pushdown没有意义
			pushdown(poi, l, r);

		if (x <= mid)
		{
			update(poi << 1, l, mid,x,y, v);
		}
		if (y > mid)
		{
			update((poi << 1) + 1, mid + 1, r,x,y, v);
		}
		a[poi] = a[poi << 1] + a[(poi << 1) + 1];//维护区间和
}

最后是query操作,获取区间和的结果,方法和update类似,但是多了一个res存储结果。

int query(int poi,int l,int r,int x,int y)
{
	int res=0;
	if (x <=l && y >=r)
	{
		return a[poi];
	}

	int mid = l + r >> 1;
	if (lazy[poi] != 0)//不为0才pushdown,为0 的话pushdown没有意义,
		pushdown(poi, l, r);

	if (x <= mid) res += query(poi << 1, l, mid, x, y);
	if (y > mid) res += query((poi << 1) + 1, mid + 1, r, x, y);
	return res;
}

整合起来,一个线段树的逻辑就写好啦~
看到这里的小伙伴,恭喜你已经对线段树有了基本的认识!!
所以……
给自己鼓个掌!!!

不过要完全掌握还需要多多练习才行。

上一篇:poi 读取word 遍历表格和单元格中的图片


下一篇:基于机器学习方法的POI品类推荐算法