【数据结构】之线段树理解与基础模板

什么是线段树

线段树 是一种通过类似 二分 来实现的一种 二叉树 结构，方便区间的修改与性质的查询，是一种非常节约时间的 数据结构 。

为什么使用线段树

比如我们给你 N N N 个数，每次可能对其中一个数进行修改，也可能询问区间 [ l , r ] [l,r] [l,r] 中的最大数，那么我们在查询区间中最大值的时候，可以很 暴力 暴力 暴力 地枚举一边，但这样的话时间复杂度很高，然后这时候我们其实也可以想到 分块 ，用这个方法来存下每个长度为 m m m 的区间的最大值，修改的时候再看是否有所改变，查询时整块儿整块儿去查询。但是时间复杂度受到块儿的大小以及每次询问时区间的边界与长度等因素的影响，十分不稳定，这时候我们就可以通过 线段树 来解决。

线段树的大致思路

1. 1. 1. 线段树 其实也是通过新建的 数组 来实现，数组 中的每个 节点 代表 原数组 中的一个 区间 。
2. 2. 2. 区间 的长度可能为 1 1 1 ，当该节点为 最底层的子节点 时，区间 的长度为 [ x , x ] [x,x] [x,x]，而 根节点代表的区间长度 为 N N N ，即 根节点 代表整个数组 [ 1 , N ] [1,N] [1,N] 的一种性质。
3. 3. 3. 对于每个 不是底层的节点 ，假设其包含区间为 [ l , r ] [l,r] [l,r]，则其 左子结点 代表 [ l , m i d ] [l,mid] [l,mid] ，右子节点 代表 [ m i d + 1 , r ] [mid+1,r] [mid+1,r] ，其中 m i d = ( l + r ) > > 1 mid = (l+r) >>1 mid=(l+r)>>1。
4. 4. 4. 若某节点在 线段树数组 中的下标为 x x x ，则其子节点在 线段树数组 中的下标分别为 x ∗ 2 x*2 x∗2 和 x ∗ 2 + 1 x*2+1 x∗2+1，有时我们也可以用位运算表示，分别为 x < < 1 x << 1 x<<1 和 x < < 1 ∣ 1 x << 1 | 1 x<<1∣1 。

当我们用区间表示时：

基础代码模板

我们这里以单点修改，区间查询最大值为例子。

线段树的声明

struct ST{int l , r , dat ;} t[N * 4];
//l和r分别表示该节点所代表区间的左右边界，dat该区间内的最大值 

线段树的建树

void build(int p , int l , int r)
{
	t[p].l = l; t[p].r = r;//记录该节点所表示的区间 
	if(l == r){return;}//此时说明是最底部节点 
	int mid = (l + r) / 2 ;
	build(p * 2 , l , mid);//建立左子结点 
	build(p * 2 + 1 , mid + 1 , r);//建立右子节点 
	t[p].dat = max(t[p * 2].dat , t[p * 2 + 1].dat);//更新区间内的最大值 
}

前文说过线段树有些 分治 的思想，那么其实也就离不开 递归 ，我们在建树的过程中相当于不断递归区间直到最底部的节点，然后向上 r e t u r n return return 来更新该区间内的最大值。

单点修改

void add(int p,int x,int v)
{
	if(t[p].l == t[p].r){t[p].dat = v ; return ;}//到达最底部节点 
	int mid = (t[p].l + t[p].r) / 2;
	if(x <= mid) add(p * 2 , x , v);//若要修改的点在该节点的左子节点 
	else add(p * 2 + 1 , x , v);//若...在右子节点 
	t[p].dat = max(t[p * 2].dat , t[p * 2 + 1].dat);//更新修改后区间的最大值 
}

区间查询最大值

int ask(int p , int l , int r)
{
	if(l <= t[p].l && r >= t[p].r) return t[p].dat;//若当前查询到的区间在询问区间范围内 
	int mid = (t[p].l + t[p].r) / 2;
	int val = -(1 << 30);
	if(l <= mid) val = max(val , ask(p * 2 , l , r));//若该区间左子结点与查询区间有重叠 
	if(r > mid) val = max(val , ask(p * 2 + 1 , l , r));//...右子节点...
	return val;//val记录该区间内的最大值，最终返还 
}

主函数中的调用

build(1 , 1 , n);//分别代表该节点在当前数组中的下标，所表示区间的左端点与右端点
add(1,b,c);//从1号节点开始，即从根节点开始，将第b个数改为c
ans = ask(1,b,c)//从1号节点开始查询，区间的左右端点分别为 b 和 c 

注

线段树 的 数组 要开 4 4 4 倍
简单基础的题可以看另一篇博客【数据结构】之树状数组与线段树的咋题题面加代码不解释