欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

浅谈线段树 Segment Tree

程序员文章站 2022-05-18 21:57:11
众所周知,线段树是algo中很重要的一项! 一.简介 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开 ......

   众所周知,线段树是algo中很重要的一项!

  一.简介

    

  线段树是一种二叉搜索树,与相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。

  使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为o(logn)。而未优化的空间复杂度为2n,实际应用时一般还要开4n的数组以免越界,因此有时需要离散化让空间压缩。浅谈线段树 Segment Tree

   二.用途

  单点 : 查询(query)修改(add,mul)

    区间 : 查询(区间和),修改,最大值(max),最小值(min)

  浅谈线段树 Segment Tree

  三. 实现方式

  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

当我们进行区间改动时

(黑色为总区间,红色为需要修改的区间)

如果当前区间是全部区间的子集————那很好,咱们可以直接修改

浅谈线段树 Segment Tree

如果当前区间和总区间有交集,那么就递归,找到第一个完全包含他的区间,然后修改,再递归上去

浅谈线段树 Segment Tree

 

上代码!!!

 

 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!