什么是线段树

线段树,是一种二叉搜索树。它将一段区间划分为若干单位区间,每一个节点都储存着一个区间。它功能强大,支持区间求和,区间最大值,区间修改,单点修改等操作。线段树的思想和分治思想很相像。

线段树的每一个节点都储存着一段区间\([L…R]\)的信息,其中叶子节点\(L=R\)。它的大致思想是:将一段大区间平均地划分成2个小区间,每一个小区间都再平均分成2个更小区间……以此类推,直到每一个区间的L等于R(这样这个区间仅包含一个节点的信息,无法被划分)。通过对这些区间进行修改、查询,来实现对大区间的修改、查询。这样一来,每一次修改、查询的时间复杂度都只为\(O(log_2n)\)。

但是,可以用线段树维护的问题必须满足区间加法,否则是不可能将大问题划分成子问题来解决的

我在此解释一下什么是满足区间加法:假设现有一区间\([L,R]\)上的问题,如果问题满足区间加法,则该问题可以由问题\([L,P]\)和\([P+1,R]\)的解得出(可以看到,这里只是说得出并不是说非要相加,所以区间加法不一定非得是加法

想必大家从上面对区间加法的解释中也看出来了,线段树也是将大问题转化成小问题来分开解决的,这不就是分治的思想吗XD。

常见的区间加法问题: 1、区间求和 \(\sum_{i=L}^Ra_i=\sum_{i=L}^Pa_i+\sum_{i=P+1}^Ra_i(L≤P<R)\) 2、区间最大值\(max_{i=L}^Ra_i=max(max_{i=L}^Pa_i,max_{i=P+1}^Ra_i)(L≤P<R)\)

显然不满足区间加法的: 1、区间的众数 2、区间的最长不下降子序列 3、……

朴素线段树的原理及实现

PS:既然我前面讲到了区间求和问题是显然的加法问题,那么下面的我就以区间求和为例来说明(很多情况下,线段树就是这个用处)

相比大家都懂二叉搜索树所以我在这不说了 线段树是二叉搜索树的一种,所以顾名思义,肯定线段树是一个二叉树!

线段树的建立方式就是把大的区间平均的拆成两端小区间(二分)进行维护,再用小区间的值的变化来更新大区间的值(朴素线段树限定版操作)。如此的操作方法对于满足区间加法的问题可以保证正确性,同时复杂度也是在\(log\)级别的。线段树要一直二分建立,直到其区间的\(L=R\),因此线段树的叶子节点一定是表示\([L,R],(L=R)\)的区间的。

因为线段树是一棵二叉树,而且除去最后一层,它是一棵满二叉树,所以其深度不会超过\(\lfloor log_2(n-1)\rfloor+2\),一般常见的比较好理解的就是递归二叉树,使用递归的方式建树,但有大佬开发了递推线段树,不会爆栈,效率更高,据说更好实现,但只能等我学会之后再说了。这里我们说递归线段树。

例如一个区间\([1,9]\),我们画出来的线段树长这样:

我相信看了这张图实现方法大家都很清楚了,那我直接上代码!

借用结构体的方式来存储

const int M=1e5+10;
struct tree{
 int l,r,sum,lazy;
}a[M];

Update函数是用于更新区间数据的,如果不要他那要线段树干嘛? Build函数是递归建立线段树的操作,其中如果\(L=R\)则停止递归。

inline void Update(int x){
	a[x].sum=a[x<<1].sum+a[x<<1|1].sum;
}

void Build(int x,int l,int r){
	a[x].l=l,a[x].r=r;
	if(l==r){
		a[x].sum=num[l];
		return ;
	}
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	Update(x);
}

线段树已经存储好了,下一步就是进行线段树应有的操作——单点修改

当我们要把下标为k的数字修改(加减乘除、赋值运算等)时,可以直接在根节点往下DFS。如果当前节点的左儿子包含下标为k的数(即对于左儿子区间\([L_{lson}…R_{lson}],L_{lson}≤k≤R_{rson}\),那么就走到左儿子,否则走到右儿子(右儿子一定包含下标为k的数,因为根节点一定包含这个数,而从根节点往下走,能到达的点也一定包含这个数),直到\(L=R\)。这时就走到了只包含k的那个节点,只需要把这个点修改即可(这个点就相当于线段树中唯一只储存着k的信息的节点)。最后记得在回溯的时候把沿途经过的所有的点的值全部修改一下(朴素线段树限定版)。

void Change(int x,int k,int t){
	if(a[x].l==a[x].r){
		a[x].sum=t;
		return ;
	}
	int mid=(a[x].l+a[x].r)>>1;
	if(k<=mid) Change(k<<1,k,t);
	else Change(k<<1|1,k,t);
	Update(x); 
}

区间修改

区间修改需要以下几步: 1、找到一个包含所有要修改区间的线段树区间 2、对区间内所有点进行修改

在第一步中,找这样一个区间要从根节点出发,向下寻找,如果要修改的区间在当前区间左部,递归到左半部分,在右部同理。但是如果遇到要修改的区间同时在左右两部分都有呢?那就把修改区间从当前区间的中部劈开。

找到了要修改的区间就该要对区间内的点做出修改。最简单的当然是\(O(n)\)直接把要修改的点的值直接改掉,但是这样复杂度是真的菜,时间复杂度达到了\(O(n^2log_2n)\),比暴力\(O(n^2)\)还慢,所以这么朴素我就不说了也不写了,直接进入优化。

懒标记

懒标记,顾名思义是用来偷懒的,可以很大程度的优化复杂度。它是一个标记,而其表现的含义是:这个区间已经被修改过了,但是下面的子区间我懒得改,我在这把修改操作告诉你,你查询的时候自己改一下就行了,别问他们,他们懒得改。

注释:标记可以分为两类1、相对标记:这种标记是可以共享的标记,和打标记的时间顺序无瓜(关),且叠加不影响答案,所以他们呢可以叠加。例如区间值的增减:对区间内数字全部+x,那么我们可以用懒标记存储x,后来又有操作对这个区间+y,那么我们就直接将标记改为\(x+y\)。 2、绝对标记:这种标记不可叠加,每一次修改都要将之前的标记下传,由它的两个儿子继续记录之前的标记,而在该节点记录新的改变。这些修改的顺序是固定的不可替换且对在线查询时答案由影响。如对区间的重新赋值等。

所以可以看出这个懒标记是与节点共存亡的,那么就直接在存储节点的结构体里再加入一个lazy的变量就可以啦。不过你要搞搞清楚你的定位,别忘了你的lazy既然只有一个,那么你得记住他是干嘛的。比如你的lazy用来给区间增减,那么lazy就记录的是加上的值(如果是减去就记负值)。很好理解,我们轻松的写出了区间修改的的代码。

//x为当前节点的编号,l,r为目标区间,t为修改操作 
void Change_Region(int x,int l,int r,ll t){
	if(a[x].l==l&&a[x].r==r){
		a[x].sum+=(r-l+1)*t;
		a[x].lazy+=t;
		return ;
	}
	Pushdown(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(r<=mid) Change_Region(x<<1,l,r,t);
	else
		if(l>mid) Change_Region(x<<1|1,l,r,t);
		else{
			Change_Region(x<<1,l,mid,t);
			Change_Region(x<<1|1,mid+1,r,t);
		}
	Update(x);
}

(这里写的是求和,是相对标记,如果是绝对标记的话,如果已经有标记,在修改之前要先下传标记)

下传标记

下传标记,顾名思义就是把标记下传。在遇到复杂情况以及绝对标记时,我们都要把懒标记下传到它的子节点去。这里假设我们要处理的问题时区间修改,即重新赋值,而不是上面的增减了。

//x为将节点x的标记下传
void Pushdown(int x){
	if(a[x].l==a[x].r){
		a[x].lazy=0;
		return ;
	}
	a[x<<1].sum=(a[x<<1].r-a[x<<1].l+1)*a[x].lazy;
	a[x<<1|1].sum=(a[x<<1|1].r-a[x<<1|1].l+1)*a[x].lazy;
	a[x<<1].lazy=a[x<<1|1].lazy=a[x].lazy;
	a[x].lazy=0;
}

这一个Pushdown是针对区间求和问题的

inline void Pushdown(int x){
	if(a[x].l==a[x].r){
		a[x].lazy=0;
		return ;
	}
	a[x<<1].sum+=(a[x<<1].r-a[x<<1].l+1)*a[x].lazy;
	a[x<<1|1].sum+=(a[x<<1|1].r-a[x<<1|1].l+1)*a[x].lazy;
	a[x<<1].lazy+=a[x].lazy;
	a[x<<1|1].lazy+=a[x].lazy; 
	a[x].lazy=0;
}

在上面的代码中我们可以看到首先计算了子节点上的sum变化,然后由子节点继承了父节点的懒标记,并清楚了父节点的懒标记,供下次使用。

区间查询

上面的都是维护线段树的部分,但是只有查询的时候线段树时有用的,所以这是很重的。线段树不查询干嘛用啊??

区间查询其实和区间修改很像,首先要递归找到你要的区间,然后取结果加起来就可以了。直接看代码。

int Query(int x,int l,int r){
	if(a[x].l==a[x].r) return a[x].sum;
	if(a[x].lazy) Pushdown(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(r<=mid) return Query(x<<1,l,r);
	if(l>mid) return Query(x<<1|1,l,r);
	return Query(x<<1,l,mid)+Query(x<<1|1,mid+1,r);
}

配上一个与题目相适的main函数就完结撒花了,这里用一个简单的线段树例题来给出代码:

https://www.luogu.org/problem/P3372 一道洛谷绿题,可简单了!

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int M=1e5+10;
typedef long long ll;
int n,m;
ll num[M];
struct Tree{
	int l,r;
	ll sum,lazy;
}a[M<<2];

inline ll Read(){
	char ch=getchar();
	ll x=0;
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

inline void Update(int x){
	a[x].sum=a[x<<1].sum+a[x<<1|1].sum;
}

//x为将节点x的标记下传
inline void Pushdown(int x){
	if(a[x].l==a[x].r){
		a[x].lazy=0;
		return ;
	}
	a[x<<1].sum+=(a[x<<1].r-a[x<<1].l+1)*a[x].lazy;
	a[x<<1|1].sum+=(a[x<<1|1].r-a[x<<1|1].l+1)*a[x].lazy;
	a[x<<1].lazy+=a[x].lazy;
	a[x<<1|1].lazy+=a[x].lazy; 
	a[x].lazy=0;
} 

void Build(int x,int l,int r){
	a[x].l=l,a[x].r=r;
	if(l==r){
		a[x].sum=num[l];
		return ;
	}
	int mid=(l+r)>>1;
	Build(x<<1,l,mid);
	Build(x<<1|1,mid+1,r);
	Update(x);
}

//x为当前节点编号,k为要修改的节点编号,t为修改后的值 
void Change(int x,int k,ll t){
	if(a[x].l==a[x].r){
		a[x].sum=t;
		return ;
	}
	int mid=(a[x].l+a[x].r)>>1;
	if(k<=mid) Change(k<<1,k,t);
	else Change(k<<1|1,k,t);
	Update(x); 
}

//x为当前节点的编号,l,r为目标区间,t为修改操作 
void Change_Region(int x,int l,int r,ll t){
	if(a[x].l==l&&a[x].r==r){
		a[x].sum+=(r-l+1)*t;
		a[x].lazy+=t;
		return ;
	}
	Pushdown(x);
	int mid=(a[x].l+a[x].r)>>1;
	if(r<=mid) Change_Region(x<<1,l,r,t);
	else
		if(l>mid) Change_Region(x<<1|1,l,r,t);
		else{
			Change_Region(x<<1,l,mid,t);
			Change_Region(x<<1|1,mid+1,r,t);
		}
	Update(x);
}

ll Query(int x,int l,int r){
	if(a[x].l==l&&r==a[x].r) return a[x].sum;
	if(a[x].lazy) Pushdown(x);	
	int mid=(a[x].l+a[x].r)>>1;
	if(r<=mid) return Query(x<<1,l,r);
	if(l>mid) return Query(x<<1|1,l,r);
	return Query(x<<1,l,mid)+Query(x<<1|1,mid+1,r);
}

int main(){
	n=Read();
	m=Read();
	for(int i=1;i<=n;i++)
		num[i]=Read();
	Build(1,1,n);
	for(int i=1;i<=m;i++){
		int op=Read();
		if(op==1){
			int x=Read(),y=Read();
			ll k=Read();
			Change_Region(1,x,y,k);
		}
		if(op==2){
			int x=Read(),y=Read();
			printf("%lld\n",Query(1,x,y));
		}
	}
	return 0;
}

//实在不好意思,第二章咕咕咕太久了,最近很忙,有空我一定更新!

0 0 votes
文章评分

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

0 评论
Inline Feedbacks
View all comments