浅谈线段树 Segment Tree
程序员文章站
2022-05-18 21:57:11
众所周知，线段树是algo中很重要的一项！ 一.简介 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开 ......
众所周知，线段树是algo中很重要的一项！
一.简介
线段树是一种二叉搜索树，与相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为o(logn)。而未优化的空间复杂度为2n，实际应用时一般还要开4n的数组以免越界，因此有时需要离散化让空间压缩。
二.用途
单点 ： 查询（query）修改（add,mul）
区间 ： 查询（区间和），修改，最大值（max)，最小值（min)。
三. 实现方式
1.建树
由于每个点都表示一个区间，所以他有很多信息（左儿子，右儿子，区间sum） 所以我们用结构体存. 因为之后要用到懒标记，所以结构体还有两个懒标记。
懒标记 ： 以上图为例，如果想在1 - 6区间内加一，我们就将这个信息从根节点传递到下一层，这时2,3点都有一个add = 1的懒标记，这样就表示已经加过1了，下次如果还要加，那么直接加在懒标记上。就比如你挣了一笔钱，暂时不用，就存在银行里了。之后如果求解需要递归，那么这个懒标记就向下传，并且传完后自己要清零！（这样更新后的状态就是 原状态 + 子区间点的个数 * 传下里的懒标记，（example sum = 5(原状态）+ 4（区间里有4个数，都加了个2） * 2（懒标记））-------很玄学
乘法的懒标记（luogu p3373）：需要特别注意下
比如 懒标记原本为2 + 3
现在传下一个乘8 那么就变为（2 + 3) * 8
然后再传一个加三，就会变成（2 + 3 + 3） * 8
所以我们这么存 2 * 8 + 3 * 8
这样加3后值才是正确的！
上代码
代码中% p 为题目要求
1 struct node {
2 int l, r;
3 ll sum;
4 ll add, mul;
5
6 node() {
7 l = r = sum = add = 0;
8 mul = 1;
9 }
10
11 void update_add(ll value) {
12 add = (add + value) % p;
13 sum = (sum + (r - l + 1) * value) % p;
14 }
15
16 void update_mul(ll value) {
17 sum = (sum * value) % p;
18 mul = (mul * value) % p;
19 add = (add * value) % p;
20 }
21 } t[n << 2];
我的建树可能比较怪，当递归到根节点再cin，一边递归一边更新（push_up,后面有）
1 void build_tree(int p, int l, int r) {
2 t[p].l = l, t[p].r = r;
3 if (l == r) {
4 cin >> t[p].sum;
5 return;
6 }
7 int mid = (t[p].l + t[p].r) >> 1;
8 build_tree(lc(p), l, mid);
9 build_tree(rc(p), mid + 1, r);
10 push_up(p);
11 }
左儿子右儿子
inline int lc(int p) {
return p << 1;
}
inline int rc(int p) {
return p << 1 | 1;
}
向上push_up更新信息（sum),向下传懒标记（push_down) 切记传完后自己状态要恢复哦！
1 void push_up(int p) {
2 t[p].sum = t[lc(p)].sum + t[rc(p)].sum;
3 }
4
5 void push_down(int p) {
6 if (t[p].mul != 1) {
7 t[lc(p)].update_mul(t[p].mul);
8 t[rc(p)].update_mul(t[p].mul);
9 t[p].mul = 1;
10 }
11 if (t[p].add) {
12 t[lc(p)].update_add(t[p].add);
13 t[rc(p)].update_add(t[p].add);
14 t[p].add = 0;
15 }
16 }
å%%%then
当我们进行区间改动时
（黑色为总区间，红色为需要修改的区间）
如果当前区间是全部区间的子集————那很好，咱们可以直接修改
如果当前区间和总区间有交集，那么就递归，找到第一个完全包含他的区间，然后修改，再递归上去
上代码！！！
1 void update1(int p, int l, int r, ll value) {//乘法更新
2 if (t[p].l >= l && t[p].r <= r) {
3 t[p].update_mul(value);
4 return;
5 }
6 push_down(p);
7 int mid = (t[p].l + t[p].r) >> 1;
8 if (l <= mid) update1(lc(p), l, r, value);
9 if (r > mid) update1(rc(p), l, r, value);
10 push_up(p);
11 }
12
13 void update2(int p, int l, int r, ll value) {//加法更新
14 if (t[p].l >= l && t[p].r <= r) {
15 t[p].update_add(value);
16 return;
17 }
18 push_down(p);
19 int mid = (t[p].l + t[p].r) >> 1;
20 if (l <= mid) update2(lc(p), l, r, value);
21 if (r > mid) update2(rc(p), l, r, value);
22 push_up(p);
23 }
24
25 ll query(int p, int l, int r) {//区间查询，如果是单点差距的话l == r
26 if (t[p].l >= l && t[p].r <= r) {
27 return t[p].sum % p;
28 }
29 push_down(p);
30 ll sum = 0;
31 int mid = (t[p].l + t[p].r) >> 1;
32 if (l <= mid) sum = (sum + query(lc(p), l, r)) % p;
33 if (r > mid) sum = (sum + query(rc(p), l, r)) % p;
34 return sum % p;
35 }
当然还可以求rmq问题
1 struct node
2 {
3 ll minn,maxx;
4 }t[];
5
6 //build 里加几句
7 t[p].maxx = max(t[lc(p)].maxx,t[rp(p)].maxx);
8 t[p].minn = min(t[lc(p)].minn,t[rp(p)].minn);
9
10
11 int ans1,ans2;
12 void new_query(int p,int l,int r)
13 {
14 if(t[p].l == l && t[p].r == r)
15 {
16 ans1 = max(ans1,t[p].maxx);
17 ans2 = max(ans2,t[p].minn);
18 return;
19 }
20 int mid = (t[p].l + t[p].r) >> 1;
21 if(r <= mid)
22 query(lc(p),l,r);
23 else if (l > mid)
24 query(rc(p),l,r);
25 else
26 {
27 query(lc(p),l,mid);
28 query(rp(p),mid + 1,r);
29 }
30 }
下面附上总代码（代码按照luogu 线段树2的模板打的，可ac）
1 #include <iostream>
2 #include<algorithm>
3 using namespace std;
4 const int n = 1e5 + 7;
5 typedef long long ll;
6
7 ll p;
8
9 struct node {
10 int l, r;
11 ll sum;
12 ll add, mul;
13 // ll minn,mmax;
14 node() {
15 l = r = sum = add = 0;
16 mul = 1;
17 }
18
19 void update_add(ll value) {
20 add = (add + value) % p;
21 sum = (sum + (r - l + 1) * value) % p;
22 }
23
24 void update_mul(ll value) {
25 sum = (sum * value) % p;
26 mul = (mul * value) % p;
27 add = (add * value) % p;
28 }
29 } t[n << 2];
30
31 inline int lc(int p) {
32 return p << 1;
33 }
34
35 inline int rc(int p) {
36 return p << 1 | 1;
37 }
38
39 void push_up(int p) {
40 t[p].sum = t[lc(p)].sum + t[rc(p)].sum;
41 }
42
43 void push_down(int p) {
44 if (t[p].mul != 1) {
45 t[lc(p)].update_mul(t[p].mul);
46 t[rc(p)].update_mul(t[p].mul);
47 t[p].mul = 1;
48 }
49 if (t[p].add) {
50 t[lc(p)].update_add(t[p].add);
51 t[rc(p)].update_add(t[p].add);
52 t[p].add = 0;
53 }
54 }
55
56 void build_tree(int p, int l, int r) {
57 t[p].l = l, t[p].r = r;
58 if (l == r) {
59 cin >> t[p].sum;
60 return;
61 }
62 int mid = (t[p].l + t[p].r) >> 1;
63 build_tree(lc(p), l, mid);
64 build_tree(rc(p), mid + 1, r);
65 // t[p].maxx = max(t[lc(p)].maxx,t[rp(p)].maxx);
66 // t[p].minn = min(t[lc(p)].minn,t[rp(p)].minn);
67 push_up(p);
68 }
69
70 void update1(int p, int l, int r, ll value) {
71 if (t[p].l >= l && t[p].r <= r) {
72 t[p].update_mul(value);
73 return;
74 }
75 push_down(p);
76 int mid = (t[p].l + t[p].r) >> 1;
77 if (l <= mid) update1(lc(p), l, r, value);
78 if (r > mid) update1(rc(p), l, r, value);
79 push_up(p);
80 }
81
82 void update2(int p, int l, int r, ll value) {
83 if (t[p].l >= l && t[p].r <= r) {
84 t[p].update_add(value);
85 return;
86 }
87 push_down(p);
88 int mid = (t[p].l + t[p].r) >> 1;
89 if (l <= mid) update2(lc(p), l, r, value);
90 if (r > mid) update2(rc(p), l, r, value);
91 push_up(p);
92 }
93
94 ll query(int p, int l, int r) {
95 if (t[p].l >= l && t[p].r <= r) {
96 return t[p].sum % p;
97 }
98 push_down(p);
99 ll sum = 0;
100 int mid = (t[p].l + t[p].r) >> 1;
101 if (l <= mid) sum = (sum + query(lc(p), l, r)) % p;
102 if (r > mid) sum = (sum + query(rc(p), l, r)) % p;
103 return sum % p;
104 }
105 /*int ans1,ans2;
106 void new_query(int p,int l,int r)
107 {
108 if(t[p].l == l && t[p].r == r)
109 {
110 ans1 = max(ans1,t[p].maxx);
111 ans2 = max(ans2,t[p].minn);
112 return;
113 }
114 int mid = (t[p].l + t[p].r) >> 1;
115 if(r <= mid)
116 new_query(lc(p),l,r);
117 else if (l > mid)
118 new_query(rc(p),l,r);
119 else
120 {
121 new_query(lc(p),l,mid);
122 new_query(rp(p),mid + 1,r);
123 }
124 }
125 */
126
127 int main()
128 {
129 int n, m;
130 cin >> n >> m >> p;
131 build_tree(1, 1, n);
132 while (m--) {
133 int op, l, r, num;
134 cin >> op >> l >> r;
135 if (op == 1 || op == 2) cin >> num;
136 if (op == 1) update1(1, l, r, num);
137 else if (op == 2) update2(1, l, r, num);
138 else cout << query(1, l, r) << endl;
139 }
140 }
141
142 //juddav007 0.0
thanks for watching!
推荐阅读
-
BZOJ3165: [Heoi2013]Segment(李超线段树)
-
浅谈线段树 Segment Tree
-
BZOJ2212: [Poi2011]Tree Rotations(线段树合并)
-
skkyk：线段树浅谈
-
线段树(segment tree)详解
-
Leetcode-307. 区域和检索 - 数组可修改 Range Sum Query - Mutable （线段树Segment Tree）-超详细Python
-
DAY5测试T2 Tree（LCA+线段树/树上差分）
-
XOR on Segment(线段树+XOR)
-
HDU - 3333 Turing Tree(线段树+离线处理)
-
HDU3333 Turing Tree(线段树 离线处理)