线段树（一）：线段树初步

什么是线段树

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

线段树的每一个节点都储存着一段区间\([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;
}