浅谈线段树 Segment Tree

时间：2024-01-25 17:55:10

　　　众所周知，线段树是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
View Code（all)

 

THANKS FOR WATCHING!

 

相关文章