线段树 | Kyons'Blog 




 
 
 
 



 
 



线段树

欢迎各大佬,大牛对本文指正,也希望本文能对各位有所帮助

本篇很多地方借鉴英雄哪里出来的博客%%%

一、基本概念

  1. 线段树是一棵二叉搜索树,它储存的是一个区间的信息。
  2. 每个节点以结构体的方式存储,结构体包含以下几个信息:每个节点以结构体的方式存储,结构体包含以下几个信息:

    (1). 区间左端点、右端点

(2). 区间所代表的值

(3). 该节点的子节点

  1. 线段树的基本思想:二分。
  2. 线段树一般结构如图所示:
    假设数据为4个数,则树应是这样word大法好
    1. 由上图可知,每个节点的

每个节点的左孩子区间范围为[left,mid],右孩子为[mid+1,right]

二、代码实现与基本操作

0.基础数据结构

1
2
3
4
5
6
7
8
9
#ifndef NULL  //防报错
#define NULL 0
#endif
typedef struct Segment_Tree* Node;
struct Segment_Tree {
int d;
int left, right;
Node lson, rson;
}*root;

1.建树 built函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node built(int left, int right)
{
Node p = new(Segment_Tree);//Node p=(Node) malloc(sizeof(Segment_Tree));,c用法
//申请一个新内存,并令p指向该处
p->left = left; //储存区间信息
p->right = right;
if (left == right) {
p->d = a[left]; //scanf("%d",&p->d),cin>>p->d,皆可,及储存数据
p->lson = NULL; //令左儿子和右儿子指向NULL
p->rson = NULL;
}
else {
int mid = (left + right) / 2; //二分
p->lson = built(left, mid); //左儿子
p->rson = built(mid + 1, right); //右儿子
p->d=p->lson->d+p->rson->d; //存储左儿子和右儿子的和
}
return p; //返回指向该处的指针
}

  除了建树,相应关闭树的函数为:

1
2
3
4
5
6
7
8
9
void close(Node p)
{
if (p != NULL) {
close(p->lson);
close(p->rson);
delete(p); //free(p);c用法
}
return;
}

非常需要注意的一件事,每次用指针建立树的时候,请务必写一个关闭清理申请的内存的函数

2. 单点查询

  (1).查找k位置的数据

1
2
3
4
5
6
7
8
9
int find(Node p, int k)
{
if (p->left == p->right&&p->left == k)
return p->d;
int mid = (p->left + p->right) / 2;
if (k <= mid)
return find(p->lson, k);
return find(p->rson, k);
}

3.单点修改

  (1).知道点所在位置,修改该点处值

1
2
3
4
5
6
7
8
9
int update(Node p, int x,int k)  //对x位置的值,进行k值的变动
{
if (p->left == p->right&&p->left == x) //如过找到了k位置
return p->d +=k; //对该点值进行操作,可以为+-*/等
int mid = (p->left + p->right) / 2; //判断该点在左区间还是右区间
if (x <= mid) //如果是左区间,只对左区间进行递归查询
return p->d = update(p->lson, x, k)+p->rson->d; //查找完后对父节点存储值进行修改
return p->d = p->lson->d+update(p->rson, x, k); //不是该点,也不在左区间,只能是右区间
}

4.区间查询

手绘的哦
  所给区间仅可能为上图四种情况。
  通过一定操作,我们都可以将上三种,全部转换为最后一种直接输出。
  闲话少说,代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
int find(Node p, int x,int y)  //注,这里假设任意x,y,都有x<y
{
if (p->left == x && p->right == y) //如果是第四种情况,直接返回
return p->d;
int mid = (p->left + p->right) / 2; //求中间值
if (y <= mid) //如果查询区间在mid左边,因为x<y<=mid
return find(p->lson, x, y); //那么直接递归左儿子
if (x > mid) //如果查询区间在mid右边,因为mid<x<y
return find(p->rson, x, y); //那么直接递归右儿子
return find(p->lson, x, mid)+find(p->rson, mid + 1, y); //两式都不符合,及x<=mid<y
//则从mid为中间值分开
//左儿子查询[x,mid],右儿子查询[mid+1,y]
}

5.区间修改

1
2
3
4
5
6
7
8
9
10
11
int update(Node p, int x, int y, int k)  //设区间为[x,y],修改的值为k
{
if (p->left == p->right && p->left == x) //如果是这个区间内的元素,就让它+k
return p->d+=k;
int mid = (p->left + p->right) / 2; //二分
if (y <= mid) //如果区间在中值的左侧
return p->d=update(p->lson, x, y,k)+p->rson->d; //仅需更新左儿子的值,并更新父亲的值
if (x > mid) //如果区间在中值的左侧
return p->d=p->lson->d+update(p->rson, x, y,k); //同上
return p->d=update(p->lson, x, mid,k) + update(p->rson, mid + 1, y,k); //如果区间被中值分开
}

三.优化

(一). Lazy-Tag懒标记

  我们考虑一下区间改值的过程:当更改某个区间的值的时候,子区间也跟着更改。显然,在大数据下,这样操作会导致TLE。
  怎么办?
  这时我们就引入一个优化方法,叫做Lazy-Tag懒标记。
  何为懒标记呢?顾名思义,就是用来偷懒的减少修改时消耗时间的。即:
  当我想要对某一区间的所有元素都+k时,在修改该区间节点时,对其打上标记lazy,并记lazy为k,修改该节点的值为+区间长度*k,立刻return,而不将该节点下面的所有子节点一一修改。

思想实现

  如图示:1~4的值分别为1,2,3,4
在这里插入图片描述
  我们选择对[1,2]区间进行修改,要求改区间所有值+2,则:在区间[1,2],打上标记lazy=2,并修改其值为3+(2-1+1)2,直接返回,并不对其子节点进行修改
纯手搓!!
  当我们再次对[1,2]区间修改时,并要求区间内所有的值+1,则:由于[1,2]有标记lazy=2,于是我们将lazy标记向其子节点传导,并修改其子节点的值。再在[1,2]区间打上lazy=1,修改值为(2-1+1)
1,返回。
手搓大法好!!!

代码实现

0.核心代码 pushdown
1
2
3
4
5
6
7
8
9
10
void pushdown(Node p)
{
if (p->lson != NULL) { //如果该节点还有后续节点
p->lson->lazy += p->lazy; //令子节点lazy继承父节点lazy,下同
p->lson->d += (p->lson->right - p->lson->left + 1)*p->lazy; //修改子节点的值,下同
p->rson->lazy += p->lazy;
p->rson->d += (p->rson->right - p->rson->left + 1)*p->lazy;
}
p->lazy = 0; //令该节点的lazy清零
}
1.树本体
1
2
3
4
5
6
7
8
9
#ifndef NULL
#define NULL 0
#endif
typedef struct Segment_Tree* Node;
struct Segment_Tree {
int d,lazy; //仅仅多了一个lazy标记
int left, right;
Node lson, rson;
}*root;
2.建树
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
Node built(int left, int right)
{
Node p = new(Segment_Tree);
p->left = left;
p->right = right;
p->lazy = 0; //只是对lazy标记进行初始化
if (left == right) {
p->d = a[left];
p->lson = NULL;
p->rson = NULL;
}
else {
int mid = (left + right) / 2;
p->lson = built(left, mid);
p->rson = built(mid + 1, right);
p->d = p->lson->d+p->rson->d;
}
return p;
}
void close(Node p)
{
if (p != NULL) {
close(p->lson);
close(p->rson);
delete(p); //free(p);c用法
}
return;
}
3.单点查询和单点修改无改变
4.区间查询
1
2
3
4
5
6
7
8
9
10
11
12
13
long long find(Node p, int x, int y)  //区间查询
{
if (p->lazy != 0) //解决一下历史遗留问题再查询
pushdown(p);
if (p->left == x && p->right == y) //其他未变
return p->d;
int mid = (p->left + p->right) / 2;
if (y <= mid)
return find(p->lson, x, y);
if (x > mid)
return find(p->rson, x, y);
return find(p->lson, x, mid)+find(p->rson, mid + 1, y);
}
5.区间修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int update(Node p, int x, int y, int k)  //区间修改
{
if (p->lazy!=0) //如果该节点的lazy不为零,就处理一下
pushdown(p);
if (p->left == x && p->right==y) { //如果是要进行修改的节点,便让该节点的lazy为k,并修改值
p->lazy = k;
return p->d += k*(y - x + 1);
}
int mid = (p->left + p->right) / 2;
if (y <= mid)
return p->d = p->rson->d+update(p->lson, x, y, k);
if (x > mid)
return p->d = p->lson->d+ update(p->rson, x, y, k);
return p->d = update(p->lson, x, mid, k) + update(p->rson, mid + 1, y, k);
}

(二). 离散化

  离散化是一个听起来很高大上的方法.
  其实做起来很简单.当然如果想高深的话,自然也拦不住
  其实就是将一串数据储存到数组中,不将数据本身作为键值,而是选择使用数组的下标作为键值.
  形象的,$1,2,3,10000000$这四个数,保存在数组$a[]$中,相对应的下标为$1,2,3,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
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <iostream>
using namespace std;
//题目中给的p
int p;
//暂存数列的数组
long long a[100007];
//线段树结构体,v表示此时的答案,mul表示乘法意义上的lazytag,add是加法意义上的
struct node {
long long v, mul, add;
} st[400007];
//buildtree
void bt(int root, int l, int r)
{
//初始化lazytag
st[root].mul = 1;
st[root].add = 0;
if (l == r) {
st[root].v = a[l];
} else {
int m = (l + r) / 2;
bt(root * 2, l, m);
bt(root * 2 + 1, m + 1, r);
st[root].v = st[root * 2].v + st[root * 2 + 1].v;
}
st[root].v %= p;
return;
}
//核心代码,维护lazytag
void pushdown(int root, int l, int r)
{
int m = (l + r) / 2;
//根据我们规定的优先度,儿子的值=此刻儿子的值*爸爸的乘法lazytag+儿子的区间长度*爸爸的加法lazytag
st[root * 2].v = (st[root * 2].v * st[root].mul + st[root].add * (m - l + 1)) % p;
st[root * 2 + 1].v = (st[root * 2 + 1].v * st[root].mul + st[root].add * (r - m)) % p;
//很好维护的lazytag
st[root * 2].mul = (st[root * 2].mul * st[root].mul) % p;
st[root * 2 + 1].mul = (st[root * 2 + 1].mul * st[root].mul) % p;
st[root * 2].add = (st[root * 2].add * st[root].mul + st[root].add) % p;
st[root * 2 + 1].add = (st[root * 2 + 1].add * st[root].mul + st[root].add) % p;
//把父节点的值初始化
st[root].mul = 1;
st[root].add = 0;
return;
}
//update1,乘法,stdl此刻区间的左边,stdr此刻区间的右边,l给出的左边,r给出的右边
void ud1(int root, int stdl, int stdr, int l, int r, long long k)
{
//假如本区间和给出的区间没有交集
if (r < stdl || stdr < l) {
return;
}
//假如给出的区间包含本区间
if (l <= stdl && stdr <= r) {
st[root].v = (st[root].v * k) % p;
st[root].mul = (st[root].mul * k) % p;
st[root].add = (st[root].add * k) % p;
return;
}
//假如给出的区间和本区间有交集,但是也有不交叉的部分
//先传递lazytag
pushdown(root, stdl, stdr);
int m = (stdl + stdr) / 2;
ud1(root * 2, stdl, m, l, r, k);
ud1(root * 2 + 1, m + 1, stdr, l, r, k);
st[root].v = (st[root * 2].v + st[root * 2 + 1].v) % p;
return;
}
//update2,加法,和乘法同理
void ud2(int root, int stdl, int stdr, int l, int r, long long k)
{
if (r < stdl || stdr < l) {
return;
}
if (l <= stdl && stdr <= r) {
st[root].add = (st[root].add + k) % p;
st[root].v = (st[root].v + k * (stdr - stdl + 1)) % p;
return;
}
pushdown(root, stdl, stdr);
int m = (stdl + stdr) / 2;
ud2(root * 2, stdl, m, l, r, k);
ud2(root * 2 + 1, m + 1, stdr, l, r, k);
st[root].v = (st[root * 2].v + st[root * 2 + 1].v) % p;
return;
}
//访问,和update一样
long long query(int root, int stdl, int stdr, int l, int r)
{
if (r < stdl || stdr < l) {
return 0;
}
if (l <= stdl && stdr <= r) {
return st[root].v;
}
pushdown(root, stdl, stdr);
int m = (stdl + stdr) / 2;
return (query(root * 2, stdl, m, l, r) + query(root * 2 + 1, m + 1, stdr, l, r)) % p;
}
int main()
{
int n, m;
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
bt(1, 1, n);
while (m--) {
int chk;
scanf("%d", &chk);
int x, y;
long long k;
if (chk == 1) {
scanf("%d%d%lld", &x, &y, &k);
ud1(1, 1, n, x, y, k);
} else if (chk == 2) {
scanf("%d%d%lld", &x, &y, &k);
ud2(1, 1, n, x, y, k);
} else {
scanf("%d%d", &x, &y);
printf("%lld\n", query(1, 1, n, x, y));
}
}
return 0;
}

练习题目

洛谷P2251
裸的RMQ问题,数据量小.
洛谷P3372
洛谷P3373
洛谷线段树模板题


 


 
 
 





 

 


 


 

 

 

 

 
 

 

 

 //删除Valine核心代码库外链调用 //调用刚下载的本地文件以加速加载速度 //这里改为从本地加载