0%

线段树

发表于 更新于 分类于
听我配图细细讲:线段树

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

用途

在 $\sf\ O(\log N)$ 的时间复杂度内实现：

单点修改、区间修改、区间查询$\sf\ etc.$

线段树维护的信息需要满足可加性，如果使用标记，标记也要满足可加性。

实现过程

基本结构与建树

有个数组 $\sf\ a={10,11,12,13,14}$ 要进行区间求和操作

怎么把这个数组存到线段树中呢？

  • 设线段树的根节点编号为 $1$

  • 用数组 $d$ 来保存我们的线段树

  • $d[i]$ 用来保存编号为 $i$ 的节点的值（这里节点的值就是这个节点所表示的区间总和）
    如图所示：

设$\sf\ d[i]$是线段树中的结点。

  • $\sf\ d[i]$ 的左节点是 $\sf\ d[ls(i)]$

  • $\sf\ d[i]$ 的右节点是 $\sf\ d[rs(i)]$

如果 $\sf\ d[i]$ 表示的是区间 $\sf\ [l,r]$

$\sf\ d[i]$ 的左儿子节点表示的是区间 $\sf\ [l, \frac{l+r}{2} ]$

$\sf\ d[i]$ 的右儿子表示的是区间 $\sf\ [ \frac{l+r}{2} +1,r]$ 。

如何实现？

如图

1
2
3
4
5
6
7
8
9
10
11
12
13
#define leaf (l==r)
void build(int l,int r,int p)
{
	if(leaf)
	{
		d[p]=a[s];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,ls(p));
	build(mid+1,r,rs(p));
	d[p]=d[ls(p)]+d[rs(p)];
}

关于线段树的空间:

如果采用$\sf\ 2p$ 是 $\sf\ p$ 的左儿子，$\sf\ 2p+1$ 是 $\sf\ p$ 的右儿子的存储方式(堆存储)，则$\sf\ d $数组的长度应为$\sf\ 2^{\left\lceil\log{n}\right\rceil+1}$，亦即取 $2$ 的幂中第一个大于等于 $\sf\ n$ 的幂并将其乘二作为$\sf\ d$数组的长度。

一般来说，开四倍是怎么样都够了的，但是在卡空间的题里要进行类似于动态开点的操作。

区间查询

区间查询，比如求区间 $\sf\ [l,r]$ 的和的操作。

比如查询区间$\sf\ [3,5]$，把 $\sf\ [3,5]$ 拆成 $\sf\ [3,3]$ 和 $\sf\ [4,5]$ 就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getsum(int l,int r,int l_now,int r_now,int p)
{
	//[l,r]为查询区间,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
	if(l<=l_now&&r_now<=r)
	{
		return d[p];//当前区间为询问区间的子集时直接返回当前区间的和
	}
	int mid=(l_now+r_now)>>1;
	int sum=0;
	if(l<=mid)
	{
		sum+=getsum(l,r,l_now,mid,ls(p));
	}
	//如果左儿子代表的区间[l,m]与询问区间有交集,则递归查询左儿子
	if(r>mid)
	{
		sum+=getsum(l,r,mid+1,r_now,rs(p));
	}
	//如果右儿子代表的区间[m+1,r]与询问区间有交集,则递归查询右儿子
	return sum;
}

主要思路是把区间拆成左右区间，再分别处理。(分治)

区间修改&懒标记

修改区间$\sf\ [l , r]$需要进行打懒标记的操作来减少时间消耗。

设一个数组 $\sf\ laz$ ， $\sf\ laz[i]$ 表示编号为 $\sf\ i$ 的节点的懒标记。

区间修改（区间加）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void interval_add(int l,int r,int val,int l_now,int r_now,int p)
{
	//[l,r]为修改区间,val为被修改的元素的变化量,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
	if(l<=l_now&&r_now<=r)
	{
		d[p]+=(r_now-l_now+1)*val;
		laz[p]+=val;
		return;
	}//当前区间为修改区间的子集时直接修改当前节点的值,然后打标记,结束修改
	int mid=(l_now+r_now)/2;
	if(laz[p]&&!leaf)
	{
		//如果当前节点的懒标记非空,则更新当前节点两个子节点的值和懒标记值
		d[ls(p)]+=laz[p]*(mid-l_now+1);
		d[rs(p)]+=laz[p]*(r_now-mid);
		
		laz[ls(p)]+=laz[p];
		laz[rs(p)]+=laz[p];//将标记下传给子节点
		laz[p]=0;//清空当前节点的标记
	}
	if(l<=mid)
	{
		interval_add(l,r,val,l_now,mid,ls(p));
	}
	if(r>mid)
	{
		interval_add(l,r,val,mid+1,r_now,rs(p));
	}
	d[p]=d[ls(p)]+d[rs(p)];
}

区间查询（求和）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int getsum(int l,int r,int l_now,int r_now,int p)
{
	//[l,r]为查询区间,[l_now,r_now]为当前节点包含的区间,p为当前节点的编号
	if(l<=l_now&&r_now<=r)
	{
		return d[p];//当前区间为询问区间的子集时直接返回当前区间的和
	}
	int mid=(l_now+r_now)>>1;
	int sum=0;
	if(l<=mid)
	{
		sum+=getsum(l,r,l_now,mid,ls(p));
	}
	//如果左儿子代表的区间[l,m]与询问区间有交集,则递归查询左儿子
	if(r>mid)
	{
		sum+=getsum(l,r,mid+1,r_now,rs(p));
	}
	//如果右儿子代表的区间[m+1,r]与询问区间有交集,则递归查询右儿子
	return sum;
}

如果要实现区间赋值，把所有 += 替换成 = 即可

(除$sum+=getsum(l,r,mid+1,r,rs(p)$ )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void interval_value(int l,int r,int val,int l_now,int r_now,int p)
{
	if(l<=l_now&&r_now<=r)
	{
		d[p]=(r_now-l_now+1)*val;
		laz[p]=val;
		return ;
	}
	int mid=(l_now+r_now)>>1;
	if(laz[p])
	{
		d[ls(p)]=laz[p]*(mid-l_now+1);
		d[rs(p)]=laz[p]*(r_now-mid);
		laz[ls(p)]=laz[rs(p)]=laz[p];
		laz[p]=0;
	}
	if(l<=mid)
	{
		interval_value(l,r,val,l_now,mid,ls(p));
	}
	if(r>mid)
	{
		interval_value(l,r,val,mid+1,r_now,rs(p));
	}
	d[p]=d[ls(p)]+d[rs(p)];
}
int getsum(int l,int r,int l_now,int r_now,int p)
{
	if(l<=l_now&&r_now<=r)return d[p];
	int mid=(l_now+r_now)>>1;
	if(laz[p])
	{
		d[ls(p)]=laz[p]*(mid-l_now+1);
		d[rs(p)]=laz[p]*(r_now-mid);
		laz[ls(p)]=laz[rs(p)]=laz[p];
		laz[p]=0;
	}
	int sum=0;
	if(l<=mid)
	{
		sum=getsum(l,r,l_now,mid,ls(p));
	}
	if(r>mid)
	{
		sum+=getsum(l,r,mid+1,r_now,rs(p));
	}
	return sum;
}

优化

  • 位运算优化

  • 递归到叶节点的时候叶节点一定包含在查询区间内，所以一定会在懒惰标记下放前就处理完$\sf\ return $，所以叶节点懒标记下放不会导致数组越界，也不用每次检查是否为叶节点了。

  • 如果懒标记不会超出数据范围，那么可以将标记永久化，永久化可以避免下传标记，降低程序常数。

小练1.LuoGu3372:线段树1

小练2.LuoGu3373:线段树2