首页 > 代码库 > 线段树再练习

线段树再练习

2024-07-02 04:18:04   227人阅读

要不是为了写splay的区间旋转的下放，我才不会写线段树的lazy下放来练练手（我原来的lazy都是跟着函数走的。。）

这个时候我们得对lazy进行重新的界定，那就是lazy对当前节点是不产生影响的，而是对它的儿子产生影响。也就是说，当我到了某一个[l,r]区间，我不仅要更新它的lazy值，还要更新本身的key值，然后在对父亲节点进行更新。具体而言，在查询和修改时，访问到某一个节点，我们就得将本身的lazy值下放，同时对儿子的key值进行更新以保证我原来的下放原则。同时根据下放的原则，那么我们就会发现，这个节点的值的更新在标记下放后就不会再次在同一次操作过程中被更新，那么就直接对于这个节点的key进行更新即可。

说那么多，还是代码比较重要！

+ View Code?
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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
typedef long long ll;
const ll maxn = 200010;
 
struct node{
    ll key,lazy;
    node *l,*r;
    node(){
        key = 0;lazy = 0; l = NULL; r = NULL;
    }
}e[maxn*3];ll ne = 0;
 
node* build(ll l,ll r){
    node* now = e + ne ++;
    if(l ^ r){
        ll mid = (l+r)>>1;
        now->l = build(l,mid);
        now->r = build(mid+1,r);
    }
    return now;
}
 
void pd(node* now,ll l,ll r){
    if(now->l != 0){
        ll mid = (l+r)>>1;
        now->l->lazy += now->lazy; now->l->key += (mid-l+1)*now->lazy;
        now->r->lazy += now->lazy; now->r->key += (r-mid)*now->lazy;
        now->lazy = 0;
    }
}
 
void add(node* now,ll l,ll r,ll ls,ll rs,ll v){
    if(ls == l && r == rs){
        now->lazy += v;
        now->key += (r-l+1)*v;
    }
    else{
        ll mid = (l+r)>>1;
        pd(now,l,r);
        if(ls >= mid+1) add(now->r,mid+1,r,ls,rs,v);
        else if(rs <= mid) add(now->l,l,mid,ls,rs,v);
        else add(now->l,l,mid,ls,mid,v),add(now->r,mid+1,r,mid+1,rs,v);
        now->key = now->l->key + now->r->key;
    }
}
 
ll ask(node* now,ll l,ll r,ll ls,ll rs){
    if(ls == l && rs == r) return now->key;
    else{
        pd(now,l,r);
        ll mid = (l+r)>>1;
        if(ls >= mid+1) return ask(now->r,mid+1,r,ls,rs);
        else if(rs <= mid) return ask(now->l,l,mid,ls,rs);
        else return ask(now->l,l,mid,ls,mid)+ask(now->r,mid+1,r,mid+1,rs);
    }
}
 
 
node* root;
ll n,m;
ll a[maxn];
 
void test(node* now,ll l,ll r){
    cout <<l <<" "<<r<<" "<<now->key<<" "<<now->lazy<<endl;
    if(l^r){
        ll mid = (l+r)>>1;
        test(now->l,l,mid);
        test(now->r,mid+1,r);
    }
}
 
int main(){
    freopen("cs.in","r",stdin);
    scanf("%lld",&n);
    root = build(1,n);
    for(ll i = 1; i <= n; i++){
        scanf("%lld",&a[i]);
        add(root,1,n,i,i,a[i]);
    }
    scanf("%lld",&m);
    while(m--){
        ll temp = 0;
        scanf("%lld",&temp);
        if(temp == 1){
            ll ls,rs,v;
            scanf("%lld%lld%lld",&ls,&rs,&v);
            add(root,1,n,ls,rs,v);
        }
        else if(temp == 2){
            ll ls,rs;
            scanf("%lld%lld",&ls,&rs);
            printf("%lld\n",ask(root,1,n,ls,rs));
        }
    }
    return 0;
}

 

 


联系
我们