这两节课学习了 线段树 这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。

什么是线段树

先来康康这类问题:
长度为$n$的数列${a_1, a_2, … , a_n}$
(1)求最值:给定$i$,$j<=n$,求${a_i, …, a_j}$区间内的最值。
(2)修改元素:给定$k$和$x$,把$a_k$改成$x$。
显然你可以用暴力去做,但是

如果在加一些操作,比如
(3)给定$n$个元素${a_1, a_2, … , a_n} $:
• 加:给定$i, j<=n$,把${a_i, …, a_j}$区间内的每个元素加$v$。
• 查询:给定$L, R<=n$,计算${a_L, …, a_R}$的区间和。

那么暴力就暴毙。。。

于是就讲了线段树。
大概长这个样子:
xds
他的每个节点都含有l和r代表了它这个节点所代表的线段或者说是区间, 所以一颗线段树就可以把一根线(一个区间)分成线段(子区间),就比如上面这颗。
对于解决区间最值的问题,每个节点多出一个num去存储当前区间的最值即可。
然后我们来看操作。

线段树的基本操作

首先我们来看个例题,Luogu P3374

例题1题面

题目描述

如题,已知一个数列,你需要进行下面两种操作:

将某一个数加上 $x$

求出某区间每一个数的和

输入格式

第一行包含两个正整数 $n,m$,分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数,其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 个整数,表示一个操作,具体如下:

1 x k 含义:将第 $x$ 个数加上 $k$

2 x y 含义:输出区间 $[x,y]$内每个数的和

输出格式

输出包含若干行整数,即为所有操作 $2$ 的结果。

这是luogu的线段树模板题1,涉及的操作有建树修改单点查询区间和

例题2题面

题目描述

如题,已知一个数列,你需要进行下面两种操作:

1.将某区间每一个数加上x

2.求出某区间每一个数的和

涉及的操作还有 区间修改

操作

建树

首先线段树是存在数组里的,数组每一个都是一个结构体
注意因为是数组存树,所以要开4被MAXN

1
2
3
4
5
struct Node
{
int l, r; //表示区间左右端点
int sum; //在本题中sum表示此区间内所有的和
}tree[4 * MaxN];

然后就是建树

1
2
3
4
5
6
7
8
9
10
11
12
int build(int index, int l, int r) // index指的是当前节点在tree数组中的位置
{
tree[index].l = l;
tree[index].r = r;
if (l == r) //如果左右端点一样说明他是一个点,更新sum为输入的值
{
tree[index].sum = input[l]; // input是输入的数组
return input[l];
}
tree[index].sum = build(lson, l, (l + r) >> 1) + build(rson, ((l + r) >> 1) + 1, r); //递归继续建树
return tree[index].sum;
}
单点修改

其实后来发现没啥用, 因为可以用区间修改的函数,l=r

1
2
3
4
5
6
7
8
9
10
11
12
void add(int index, int x, int k)
{
tree[index].sum += k;//只要是遍历到的节点都要加K

if (tree[index].l == tree[index].r) return;

if (x <= tree[index << 1].r) //遍历左子树
add(index << 1, x, k);

if (x >= tree[(index << 1) + 1].l) //遍历右子树 index << 1 等价于 index * 2 但是位运算更快
add((index << 1) + 1, x, k);
}
区间查询(无懒标记)

区间查询就是,每查到一个区间,有三种选择:

1、如果这个区间被完全包括在目标区间内,那么加上这个区间的和,然后return;

2、如果这个区间的right>目标区间的left,那么查询这个区间;

3、如果这个区间的left<目标区间的right,也查询这个区间;

1
2
3
4
5
6
7
8
9
10
11
12
13
void searchlr(int index, int left, int right)
{
if (tree[index].l >= left && tree[index].r <= right) //此节点被要查询的区间包含
{
ans += tree[index].sum;
return;
}

if (tree[index << 1].r >= left) //要查询的区间有部分在左子树
searchlr(index << 1, left, right);
if (tree[(index << 1) + 1].l <= right) //要查询的区间有部分在右子树
searchlr((index << 1) + 1, left, right);
}

例题1代码综上即可,总的就不放了,因为太乱了

区间修改

然后便是例题2,这一题不同于前一题,因为涉及了区间修改,那么就要涉及另一个东西:LazyTag

LazyTag我感觉跟图片懒加载有点像,就是不涉及真正使用是不需要深入加载

首先,懒标记的作用是记录每次、每个节点要更新的值,优点在于传递式记录而不是全记录(全记录还是很慢)

当执行区间修改操作时:
若整个区间都被操作时,记录在公共祖先节点上;只修改了一部分,那么就记录在这部分的公共祖先上;如果只修改了自己的话,那就只改变自己。

之后,如果我们采用上述的优化方式的话,我们就需要在每次区间的查询修改时pushdown一次,以免重复或者冲突或者爆炸qwq

至于pushdown,就是将节点的lazytag信息向下传递

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
void pushdown(int index)
{
if (tree[index].tag) //如果有信息
{
tree[index << 1].sum += tree[index].tag * (tree[index << 1].r - tree[index << 1].l + 1); //把左子树的sum加上
tree[(index << 1) + 1].sum += tree[index].tag * (tree[(index << 1) + 1].r - tree[(index << 1) + 1].l + 1); //把右子树的sum加上
tree[index << 1].tag += tree[index].tag; //将懒标记信息传递
tree[(index << 1) + 1].tag += tree[index].tag;
tree[index].tag = 0; //清零本节点标记^.^
}
}

void addlr(int index, int left, int right, int k)
{
if (tree[index].l >= left && tree[index].r <= right)
{
tree[index].sum += (long long) k * (tree[index].r - tree[index].l + 1);
tree[index].tag += k; // lazy tag
return;
}
//如果区间修改的区间没有包含本区间,那就要更新一次懒标记,不然下一层算的时候会出锅
pushdown(index);
if (tree[index << 1].r >= left)
addlr(index << 1, left, right, k);
if (tree[(index << 1) + 1].l <= right)
addlr((index << 1) + 1, left, right, k);

tree[index].sum = tree[index << 1].sum + tree[(index << 1) + 1].sum; //最后回来累计上
}
区间查询(有懒标记)

还是分块思想,每查到一个区间,有三种选择:

1、如果这个区间被完全包括在目标区间内,那么加上这个区间的和,然后return;

pushdown(很重要)

2、如果这个区间的right>目标区间的left,那么查询这个区间;

3、如果这个区间的left<目标区间的right,也查询这个区间;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void searchlr(int index, int left, int right)
{
if (tree[index].l >= left && tree[index].r <= right)
{
ans += tree[index].sum;
return;
}

spread(index);//不要忘记传递信息

if (tree[index << 1].r >= left)
searchlr(index << 1, left, right);
if (tree[(index << 1) + 1].l <= right)
searchlr((index << 1) + 1, left, right);
}

然后就完事了!!!

那我们来做到题目吧
不,我不想做题目
四倍经验,一次满足😲
哦??

线段树的小题目

Luogu P2574

题目描述

AKN 觉得第一题太水了,不屑于写第一题,所以他又玩起了新的游戏。在游戏中,他发现,这个游戏的伤害计算有一个规律,规律如下

拥有一个伤害串,是一个长度为 $n$ 的只含字符 0 和字符 1 的字符串。规定这个字符串的首字符是第一个字符,即下标从 $1$ 开始。

给定一个范围 $[l, r]$,伤害为伤害串的这个范围内中字符 1 的个数

会修改伤害串中的数值,修改的方法是把 $[l, r]$ 中所有原来的字符 0 变成 1,将 1 变成 0

AKN 想知道一些时刻的伤害,请你帮助他求出这个伤害。

题解!

首先这是一道线段树的题,那么线段树的节点都记录了什么呢?
首先是左右端点(废话,但是cjc巨佬告诉我可以不用l,r),然后是sum代表该区间1的数量,tag懒标记其实就是此区间变不变,因为翻来翻去就回来了
因为是01变化,所以反转后1的个数就等于区间长度-原本1的个数
其他的操作和线段树差不多,要注意的是pushdown的思路(有点小坑):

1
2
3
4
5
6
7
8
9
10
11
void pushdown(int index)
{
if (tree[index].tag)
{
tree[lson].sum = (tree[lson].r - tree[lson].l + 1) - tree[lson].sum; //更新左子树,左子树翻转
tree[rson].sum = (tree[rson].r - tree[rson].l + 1) - tree[rson].sum; //右
tree[lson].tag ^= 1; //更新左右子树信息,0变1,1变0
tree[rson].tag ^= 1;
tree[index].tag = 0;
}
}

总体代码如下

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
#include <bits/stdc++.h>
#define MaxN 200000 + 9
#define lson index << 1
#define rson index << 1 | 1

using namespace std;

struct Node
{
int l, r;
int sum;
bool tag = 0;
}tree[4 * MaxN];//不要忘记开4倍

int n, m, input[MaxN], ans = 0;

int build(int index, int l, int r)
{
tree[index].l = l;
tree[index].r = r;
if (l == r)
{
tree[index].sum = input[l];
return input[l];
}
tree[index].sum = build(lson, l, (l + r) >> 1) + build(rson, ((l + r) >> 1) + 1, r);
return tree[index].sum;
}

void pushdown(int index)
{
if (tree[index].tag)
{
tree[lson].sum = (tree[lson].r - tree[lson].l + 1) - tree[lson].sum;
tree[rson].sum = (tree[rson].r - tree[rson].l + 1) - tree[rson].sum;
tree[lson].tag ^= 1;
tree[rson].tag ^= 1;
tree[index].tag = 0;
}
}

void add(int index, int l, int r)
{
if (tree[index].l >= l && tree[index].r <= r)
{
tree[index].sum = (tree[index].r - tree[index].l + 1) - tree[index].sum;
tree[index].tag ^= 1;
return;
}

pushdown(index);
if (tree[lson].r >= l)
add(lson, l, r);
if (tree[rson].l <= r)
add(rson, l, r);
tree[index].sum = tree[lson].sum + tree[rson].sum;
return;
}

void ask(int index, int l, int r)
{
if (tree[index].l >= l && tree[index].r <= r)
{
ans += tree[index].sum;
return;
}
pushdown(index);
if (tree[lson].r >= l)
ask(lson, l, r);
if (tree[rson].l <= r)
ask(rson, l, r);
}

int main()
{
char ch[MaxN];
scanf("%d%d", &n, &m);
scanf("%s", &ch);
for (int i = 0; i < n; ++i)
{
input[i + 1] = ch[i] ^ 48;
}
//输入
build(1, 1, n);//建树
for (int i = 1; i <= m; ++i)
{
int a, b, c;
scanf("%d", &a);
if (a == 0)//变换
{
scanf("%d%d", &b, &c);
add(1, b, c);
}
if (a == 1)//查询、输出
{
ans = 0;
scanf("%d%d", &b, &c);
ask(1, b, c);
printf("%d\n", ans);
}
}
return 0;
}

四倍经验!!!

做出这一题,剩下的这几题思路一摸一样,只用注意一下各个题目的初始条件和查询方式即可
然后就可以收获好多AC啦!!!

总结

发现线段树理清了思路还是挺好打的一个数据结构,但是要注意的事情还是挺多的,毕竟比较长:
1.tree数组要开4倍
2.建议用宏定义进行一波lson rson什么的定义,不然可能会打到崩溃
3.暂时好像没啥了

总之,你看这个代码它又长又宽,就像这个鼠标它又大又圆(大雾) 希望大家都可以熟练运用线段树!

评论