线段树(Segment Tree)入门

线段树的作用&原理

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

以上内容摘抄自百度百科.

先从最基础的内容开始:

给出一个序列 (a),支持个序列中某个位置的数加上一个数,查询区间之和(这个应该算是树状数组的模板题,但是线段树也可以解决).

暴力的方法想必是非常简单,但是时间复杂度是 (O(N^2)) 的,并不是很优秀,于是就可以用到线段树来维护.

线段树是一颗二叉树,大概张这样:

在这里插入图片描述

对于每一个节点都需要维护一些信息,其中叶节点维护的就是一个序列,可以这样认为,对于一棵维护序列的线段树从左到右的叶节点就是这个序列.

对于每一个非叶节点通常都有两个子节点,这个节点维护的信息就是这由两个叶节点的信息合并而来,所以线段树并不是刻意维护所有的信息,它维护的信息必须支持合并,例如在本题中区间和就是一个很好合并的信息(只需要相加就好了)但是也存在一些看起来不是很好合并的信息经过一定的变换后也变得可以合并.(例如区间平方和,立方和...)

还有一个问题,那就是这颗树需要存储,可能会想到用一个二维数组,但这显然非常浪费空间,于是可以将这样的一颗二叉树放入一个数组中,每个节点都要有一个独一无二的编号,可以发现第 (i) 行的节点个数为 (2^{i-1}) 个,于是对于节点编号为 (now) 的节点它的子节点编号为 (now*2) 和 (now*2+1) 时不会出现浪费,也不会出现重复了.

代码的实现

知道了大概原理之后就是要用代码来实现了.

合并子节点信息(PushUp)

void PushUp(int now)
{
	sgt[now].sum=sgt[now*2].sum+sgt[now*2+1].sum;//只需要查询区间和,所以只需要将两颗子树的和相加就好了
}

建树(Build)

void Build(int now,int left,int right)
{
	if(left==right)
	{
		sgt[now]=arr[left];
		return;
	}
	int middle=(left+right)/2;//为了保证时间复杂度,需要让同一层每个节点维护的序列长度尽可能相等
	Build(now*2,left,middle);
	Build(now*2+1,middle+1,right);
	PushUp(now);//合并信息
}

修改(Updata)

void Updata(int place,int add,int now,int left,int right)
{
	if(place<left&&right<place)//如果当前的区间并没有包含需要修改的位置自然不会产生影响,可以直接return
	{
		return;
	}
	if(left==right)//当叶节点时就可以直接单点修改了
	{
		sgt[now].sum+=add;
		return;
	}
	int middle=(left+right)/2;
	//需要修改左右子树
	Updata(place,add,now*2,left,middle);
	Updata(place,add,now*2+1,middle+1,right);
	PushUp(now);//合并
}

修改的时间复杂度证明,因为每一层的区间大小都会除以二,当区间大小为 (1) 时最多只有 (log_2N) 层,所以修改的时间复杂度是 (O(log_2N)).

查询(Query)

int Query(int now_left,int now_right/*需要查询的范围*/,int now,int left,int right)
{
	if(now_right<left||right<now_left)//如果当前的范围并没有包括需要查询的范围直接可以返回0,但是并不是所有时候都是返回0,这里需要返回一个队最终答案没有影响的值.
	{
		return 0;
	}
	if(now_left<=left&&right<=now_right)
	{
		return sgt[now].sum;
	}
	int middle=(left+right)/2;
	return Query(now_left,now_right,now*2,left,middle)+Query(now_left,now_right,now*2+1,middle+1,right);//将左右子树的值相加后返回
}

Lazy标记&PushDown

将刚才的那道题目升级一下,将单点修改改为区间修改(区间中的每个数同时加上一个相同的数),那么需要怎么办呢?

这时就出现了一种神奇的标记Lazy标记,可以发现如果区间修改用暴力去写的话需要 (O(N)) 的时间复杂度(和建树同理),这显然又不优秀了,而lazy标记就可以解决这个问题,对于每一次区间修改的时候,将这个区间分成若干段不相交的区间,每一段区间上可以直接修改区间和,再打上一个标记,表示以这个位置为根节点的子树中每一个节点都需要加上这个数,只有当需要修改(查询)当前树子树时再将标记下传,这也就可以保证修改的时间复杂度为 (O(log_2N)) 了.

下传标记PushDown

void Down(LazyTag tag,int now,int left,int right)//区间修改
{
	sgt[now].tag.add=sgt[now].tag.add+tag.add;//在lazy标记上加上新的标记
	sgt[now].sum=sgt[now].sum+(right-left+1)*tag.add;//在去加中的每个数都加上标记后的值计算出来
}
void PushDown(int now,int left,int right)//下传
{
	if(sgt[now].tag.add)//如果当前的位置有标记
	{
		Down(sgt[now].tag,LEFT);//给子节点加上这个标记
		Down(sgt[now].tag,RIGHT);
		sgt[now].tag.CleanLazyTag();//清空标记
	}
}

小结

本文重新写了一下线段树入门的内容,比较适合初学线段树的同学看,看完以后请点击我.