本文原文链接为线段树入门,转载请注明原文连接并附此声明。

蒟蒻刚学完线段树不久,写一篇线段树入门笔记。

线段树是一种二叉搜索树,是 $OI$ 中很重要的数据结构。其支持单点修改,区间修改,单点查询,区间查询(最大最小值、求和)等操作。虽然比树状数组慢,但是它支持的操作更多。

线段树可以高效地解决具有区间性质的问题,例如区间求和,一次操作(修改,查询)就要遍历整个数组,单次操作时间复杂度 $O(n)$ ,$q$ 次修改复杂度 $O(nq)$ ,远远超时。而线段树单次修改时间复杂度 $O(\log n)$ , $q$ 次修改复杂度 $O(q \log n)$ ,节约的不少时间。

线段树基本结构

比如一个长度为 $5$ 的集合 ${8,3,11,4,13}$ ,要维护他它的区间总和,建造出的线段树如下图所示:

线段树示例

如图所示,线段树的性质如下:

  • $1.$ 线段树的每一个节点都管理着一段区间,其值为这一区间内需要维护的值,根节点(编号为 $1$ )管理着整段区间 $[1,n]$ ,叶子节点管理的区间长度为 $1$ 。

  • $2.$ 除叶子节点外,其他节点分别有两个子节点,如当前节点的编号为 $p$ ,则左子节点的编号为 $2p$ ,右子节点的编号为 $2p+1$ 。

  • $3.$ 如节点 $p$ 的管理区间为 $[l,r]$ ,设此区间的中点为 $mid$ ,则左子节点管理区间的范围是 $[l,mid]$ ,右子节点管理区间的范围是 $[mid+1,r]$ 。

线段树建树

这里以维护区间总和为例子。

我们考虑每个节点需要储存的信息有:当前节点管理区间的左右端点,维护的值,以及标记等(后面会讲到),我们可以用一个结构体存储。

代码:

1
2
3
4
struct Node{
int l,r; //左右端点
long long sum; //维护总和
}tree[4*n];

线段树空间一定要开原数组的4倍,不然很有可能爆空间。

因为树具有天然的递归性质,所以我们可以用递归建树。如果当前节点是叶子节点,那么将其赋值为当前区间的值,否则递归build一下左子树,再build一下右子树,最后回传一下左右子节点的 $sum$ 就可以了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
//p为当前节点编号,l为当前区间起点,r为当前区间终点
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r; //当前树的管理区间范围
if(l==r){
tree[p].sum=a[l]; //叶子节点直接赋值
return;
}
int mid=(l+r)/2; //区间中点
build(p*2,l,mid); //递归建左子树
build(p*2+1,mid+1,r); //递归建右子树
pushup(p); //回传sum
}

回传pushup的时候,对于区间性质的问题来说,就是将左右两个节点的答案合并就可以了。

示例图:

pushup回传

区间求和公式如下:

区间最大/最小值公式如下:

代码:

1
2
3
4
//p为当前节点编号
void pushup(int p){
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

建树时间复杂度可以估计为 $O(n)$ ,因为需要遍历所有的节点。

线段树单点修改

比如要将$a_x$ 的数值修改,就是将线段树中区间起点为 $x$ 且长度为 $1$ 的节点修改,然后再回传回根节点,那么整体的思路如下:

  • $1.$ 从根节点出发,往下寻找目标节点,修改其值。

  • $2.$ 将总和回传到根节点。

举个例子,还是之前的集合 ${8,3,11,4,13}$ ,现要将第 $2$ 个数 $3$ 加上 $6$ ,操作如下图所示:

找到修改节点

修改回传

我们可以考虑使用递归实现。如果是目标节点,那么修改,然后return,否则递归向下,目标在左边就遍历左子树,目标在右边就遍历右子树,最后回传总和就可以了。

代码:

1
2
3
4
5
6
7
8
9
10
11
//p为当前节点编号,x为要修改的位置,k为要加上的值
void update(int p,int x,int k){
if(tree[p].l==tree[p].r){ //要修改的节点
tree[p].sum+=k; //直接修改,返回
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid)update(p*2,x,k); //在左子树,递归到左边
if(x>mid)update(p*2+1,x,k); //在右子树,递归到右边
pushup(p); //回传sum
}

单点修改的时间复杂度为 $O(\log n)$ ,因为向下递归到叶子节点是遍历树的深度。

线段树区间查询

单点查询没什么可说的吧,和单点修改类似,我们主要看一下区间查询。

区间查询分为三种情况:

  • $1.$ 当前节点的区间包含在查询区间之内,直接返回当前节点的 $sum$ 值。
  • $2.$ 当前区间与左子树区间有重叠部分,那么递归搜索左子树,加上答案。
  • $3.$ 当前区间右子树区间有重叠部分,那么递归搜索右子树,加上答案。

还是之前那个例子,比如查询区间 $[2,4]$ ,如下图所示:

一般来说查询要加long long,因为所有数的总和有可能爆int

代码:

1
2
3
4
5
6
7
8
9
10
11
//p为当前节点编号,l为查询区间的左端点,r为查询区间的右端点
long long query(int p,int l,int r){
if(tree[p].l>=l&&tree[p].r<=r){ //在查询区间内
return tree[p].sum; //直接返回值
}
long long ans=0;
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid)ans+=query(p*2,l,r); //如果左子树区间有重叠部分,答案加上左边的查询
if(r>mid)ans+=query(p*2+1,l,r); ////如果右子树区间有重叠部分,答案加上右边的查询
return ans;
}

区间的时间复杂度为 $O(\log n)$ ,因为每次查询都要将线段树一分为二,最后会分成 $\log n$ 个部分。

P3374 【模板】树状数组 1

虽然此题的题目看起来和线段树毫不相干,但是这可以用线段树去做。

这是一个线段树单点修改,区间查询的模板题。

代码:

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
struct Node{
int l,r; //左右端点
long long sum; //维护总和
}tree[4*500010];
int n,m,a[500010];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-48;ch=getchar();
}
return x*f;
}
void pushup(int p){
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}
void build(int p,int l,int r){
tree[p].l=l,tree[p].r=r; //当前树的管理区间范围
if(l==r){
tree[p].sum=a[l]; //叶子节点直接赋值
return;
}
int mid=(l+r)/2; //区间中点
build(p*2,l,mid); //递归建左子树
build(p*2+1,mid+1,r); //递归建右子树
pushup(p); //回传sum
}
void update(int p,int x,int k){
if(tree[p].l==tree[p].r){ //要修改的节点
tree[p].sum+=k; //直接修改,返回
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(x<=mid)update(p*2,x,k); //在左子树,递归到左边
if(x>mid)update(p*2+1,x,k); //在右子树,递归到右边
pushup(p); //回传sum
}
long long query(int p,int l,int r){
if(tree[p].l>=l&&tree[p].r<=r){ //在查询区间内
return tree[p].sum; //直接返回值
}
long long ans=0;
int mid=(tree[p].l+tree[p].r)/2;
if(l<=mid)ans+=query(p*2,l,r); //如果左子树区间有重叠部分,答案加上左边的查询
if(r>mid)ans+=query(p*2+1,l,r); ////如果右子树区间有重叠部分,答案加上右边的查询
return ans;
}
int main(){
n=read(),m=read();
for(int i=1;i<=n;i++){
a[i]=read();
}
build(1,1,n); //从根节点出发,建造 [1,n] 区间的线段树
while(m--){
int op,x,y;
op=read(),x=read(),y=read();
if(op==1){
update(1,x,y); //从根节点出发,区间 [x,x] 的值 +y
}
else{
long long ans=0;
printf("%lld\n",query(1,x,y)); //从根节点出发,查询区间 [x,y] 的总和
}
}
return 0;
}

因为需要操作 $m$ 次,所以整体时间复杂度为 $O(m \log n)$ 。

线段树区间修改

要把线段树的一段区间修改为某个值,最简单、最暴力的方法是遍历每一个节点暴力单点修改。

但是这种方法的时间复杂度是炸的,单次暴力区间修改时间复杂度 $O(n \log n)$ ,$q$ 次修改时间复杂度 $O(q·n \log n)$ ,甚至比直接暴力循环修改的时间复杂度还多一个 $\log$ 。

为什么这样子复杂度这么高呢?我们可以画个图。集合 ${8,3,11,4,13}$ ,区间 $[1,3]$ 统一加 $5$ ,要修改到的节点如下图所示:

总之可以看到,画绿线的节点都是修改区间下的子节点,其实完全没有逐一修改的必要。我们可以先让区间节点修改了,再加上一个“懒”标记,查询时再下传到子节点里面,这样可以大幅提升效率。

“懒”标记指的是当前节点修改过了,但没有让下边的节点修改的一种标记,可以再查询时需要时下传,大大节省时间,所以是懒标记。

最后

好了,就暂时先写到这里吧,因为这个蒟蒻要卷whk干其他事,就先咕咕了。

已知错误:

由于这个蒟蒻的知识短浅疏忽,误将树形视图的方括号写成了圆括号,因为太多改不过来了。

请各位大佬帮忙指出文章的问题,以免误人子弟。