线段树详解

什么是线段树？

1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。

2、每个节点以结构体的方式存储，结构体包含以下几个信息：

?????区间左端点、右端点；（这两者必有）

?????这个区间要维护的信息（事实际情况而定，数目不等）。

3、线段树的基本思想：二分

4、线段树一般结构如图所示：

5、特殊性质：

由上图可得，

1、每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]

2、对于结点k，左孩子结点为2*k，右孩子为2*k+1，这符合完全二叉树的性质

线段树模版：

1.定义线段树结构体类型：

#define SIZE 1e5+3
struct tree{
    int l,r;//线段树结点的左右区间
    int dat;//线段树节点的存储数据
}t[int(SIZE)*4];//结构体要开4倍空间，为啥自己画一个[1,10]的线段树就懂了

注意 ：

本文中线段树的dat使用的是区间最大和，具体定义需要视题目情况而论。

---

2.建立一个二叉树：

void build(int num,int l,int r){
	t[num].l=l,t[num].r=r;
	if(l==r){
		t[num].dat=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(num*2,l,mid);
	build(num*2+1,mid+1,r);
	t[num].dat=max(t[num*2].dat,t[num*2+1].dat);
}

---

?3.查询：?

①主体思路：与二分查询法基本一致，如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。如果不是，因为这是二分法,所以设查询位置为x，当前结点区间范围为了l，r，中点为mid，则如果x<=mid，则递归它的左孩子，否则递归它的右孩子。

②代码：

void ask(int k)
{
? ? if(tree[k].l==tree[k].r) //当前结点的左右端点相等，是叶子节点，是最终答案?
? ? {
? ? ? ? ans=tree[k].w;
? ? ? ? return ;
? ? }
? ? int m=(tree[k].l+tree[k].r)/2;
? ? if(x<=m) ask(k*2);//目标位置比中点靠左，就递归左孩子?
? ? else ask(k*2+1);//反之，递归右孩子?
}

③正确性分析：

?????因为如果不是目标位置，由if—else语句对目标位置定位，逐步缩小目标范围，最后一定能只到达目标叶子节点。

好的本文就到这里

4.单点修改，即更改某一个点的状态。用引例中的例子，对第x个数加上y

①主体思路

?结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态。

?②代码：?

好的本期关于线段树的讲解到此结束，请大家多多为我的主页中的“2023我的编程之旅”多多点赞评论呀！