线段树学习笔记

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 4.7k | 阅读时长 ≈ 4 分钟

1.线段树的作用

给定一个整数序列，让你完成如下操作

  • 修改序列上某个位置（区间）上的数

  • 询问序列中某个区间的和

    “暴力”算法

  • 单点修改$O(1)$

  • 询问区间和$O(区间长度)$

    “前缀和”算法

  • 单点修改$O(区间长度)$

  • 询问区间和$O(1)$

    线段树

    $O(nlogn)$

2.线段树的概念

线段树是一棵二叉树，树上的每个结点对应序列的一段区间

3.线段树的操作

1.结构体

1
2
3
4
struct node
{
    int l,r,w,f;//l,r代表左，右端点，w代表这一段区间和，f是懒标记（懒标记在之后会提到）
}tree[4*n];//线段树要开到4倍的空间

2.建树

基本思想：

  • 1 二分

  • 2 对于二分到的每一个结点，把左右端点的信息储存

  • 3 叶结点输入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    void build(int l,int r,int k)
    {
    	tree[k].l =l,tree[k].r =r;
    	if(tree[k].l==tree[k].r)//叶子结点
    	{
    		scanf("%d",&tree[k].w);
    		return;
    	}
    	int m=(l+r)/2;
    	build(l,m,k*2);//左孩子
    	build(m+1,r,k*2+1);//右孩子
    	tree[k].w =tree[k*2].w +tree[k*2+1].w ;//合并
    }

3.单点查询

1
2
3
4
5
6
7
8
9
10
11
12
void ask(int k)
{
	if(tree[k].l ==tree[k].r )//是目标结点
	{
		ans=tree[k].w ;//储存答案
		return;
	}
	if(tree[k].f ) down(k);//下传懒标记
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) ask(k*2);//在左边递归左孩子
	else ask(k*2+1);//在右边递归右孩子
}

4.单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
void add(int k)
{
	if(tree[k].l ==tree[k].r )//是目标结点
	{
		tree[k].w +=y;//修改
		return;
	}
	if(tree[k].f ) down(k);//懒标记下传
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) add(k*2);//在左边递归左孩子
	else add(k*2+1);//在右边递归右孩子
	tree[k].w =tree[k*2].w +tree[k*2+1].w ;//状态修改
}

5.区间求和

1
2
3
4
5
6
7
8
9
10
11
12
void sum(int k)
{
	if(tree[k].l >=x&&tree[k].r <=y)//左右端点全在目标区间内
	{
		ans+=tree[k].w ;//答案直接加上这一段区间和
		return;
	}
	if(tree[k].f ) down(k);//懒标记下传
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) sum(k*2);//往左孩子移
	if(y>m) sum(k*2+1);//往右孩子移
}

6.区间修改

在前面的操作中我们经常看到有懒标记下传这个操作，那么懒标记到底是什么呢

1.1懒标记的作用

存储到这个节点的更新信息，暂时不把更新信息传到子节点。

1.2懒标记的下传

  • 1 将当前节点的懒标记累加到子节点的懒标记中

  • 2 修改子节点状态，即区间和$w$=原状态+区间长度×父节点下传的懒标记

  • 3 父节点懒标记清空

    1
    2
    3
    4
    5
    6
    7
    8
    void down(int k)
    {
    	tree[k*2].f +=tree[k].f ;//修改子节点懒标记(下同)
    	tree[k*2+1].f +=tree[k].f ;
    	tree[k*2].w +=tree[k].f *(tree[k*2].r -tree[k*2].l +1);//修改子节点状态(下同)
    	tree[k*2+1].w +=tree[k].f *(tree[k*2+1].r -tree[k*2+1].l +1);
    	tree[k].f =0;//懒标记清零
    }

2.区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void add2(int k)//y为增加的数，(a,b)为目标区间
{
	if(tree[k].l >=a&&tree[k].r <=b)//在目标左右端点内
	{
		tree[k].w +=(tree[k].r -tree[k].l +1)*y;//状态修改
		tree[k].f +=y;//懒标记加上y
		return;
	}
	if(tree[k].f) down(k);//懒标记下传
	int m=(tree[k].l +tree[k].r )/2;
	if(a<=m) add2(k*2);//如区间求和(下同)
	if(b>m) add2(k*2+1);
	tree[k].w =tree[k*2].w +tree[k*2+1].w ;//修改状态
}

4.完整代码

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long l,r,w,f;
} tree[400001];
long long ans,x,y,a,b,n,p,m;
void build(int l,int r,int k)//建树 
{
	tree[k].l =l,tree[k].r =r;
	if(tree[k].l==tree[k].r)
	{
		scanf("%lld",&tree[k].w);
		return;
	}
	int m=(l+r)/2;
	build(l,m,k*2);
	build(m+1,r,k*2+1);
	tree[k].w =tree[k*2].w +tree[k*2+1].w ;
}
void down(int k)//懒标记下传 
{
	tree[k*2].f +=tree[k].f ;
	tree[k*2+1].f +=tree[k].f ;
	tree[k*2].w +=tree[k].f *(tree[k*2].r -tree[k*2].l +1);
	tree[k*2+1].w +=tree[k].f *(tree[k*2+1].r -tree[k*2+1].l +1);
	tree[k].f =0;
}
void ask(int k)//单点查询 
{
	if(tree[k].l ==tree[k].r )
	{
		ans=tree[k].w ;
		return;
	}
	if(tree[k].f ) down(k);
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) ask(k*2);
	else ask(k*2+1);
}
void add(int k)//单点修改加法 
{
	if(tree[k].l ==tree[k].r )
	{
		tree[k].w +=y;
		return;
	}
	if(tree[k].f ) down(k);
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) add(k*2);
	else add(k*2+1);
	tree[k].w =tree[k*2].w +tree[k*2+1].w ;
}
void sum(int k)//区间求和 
{
	if(tree[k].l >=x&&tree[k].r <=y)
	{
		ans+=tree[k].w ;
		return;
	}
	if(tree[k].f ) down(k);
	int m=(tree[k].l +tree[k].r )/2;
	if(x<=m) sum(k*2);
	if(y>m) sum(k*2+1);
}
void add2(int k)//区间修改加法 
{
	if(tree[k].l >=a&&tree[k].r <=b)
	{
		tree[k].w +=(tree[k].r -tree[k].l +1)*y;
		tree[k].f +=y;
		return;
	}
	if(tree[k].f) down(k);
	int m=(tree[k].l +tree[k].r )/2;
	if(a<=m) add2(k*2);
	if(b>m) add2(k*2+1);
	tree[k].w =tree[k*2].w +tree[k*2+1].w ;
}
int main()
{
	scanf("%lld%lld",&n,&m);//n个数和m个操作
	build(1,n,1);//建树
	for(int i=1; i<=m; i++)
	{
		scanf("%lld",&p);
		ans=0;
		switch(p)
		{
			case 1:{//1为单点查询
				cin >> x;
				ask(1);
				printf("%lld\n",ans);
				break;
			}
			case 2:{//2为单点修改
				cin >> x >> y;
				add(1);
				break;
			}
			case 3:{//3为区间求和
				cin >> x >> y ;
				sum(1);
				printf("%lld\n",ans);
				break;
			}
			case 4:{//4为区间修改
				cin >> a >> b >> y;
				add2(1);
				break;
			}
		}
	}
	return 0;
}

5.推荐例题

思路点拨：线段树模板

思路点拨：线段树模板