Competitive-Programming/template/SegTreeLz.cpp at master · HanaYukii/Competitive-Programming · GitHub

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
// Segment Tree with Lazy Propagation
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
const int mod = 1e9+7;
long long lz[MAXN<<2];
long long mx[MAXN<<2];
void pushdown(int x){
    if(!lz[x])return ;
    lz[x<<1] += lz[x];
    lz[x<<1|1] += lz[x];
    mx[x<<1] += lz[x];
    mx[x<<1|1] += lz[x];
    lz[x] = 0;
}
void pushup(int x){
    mx[x] = max(mx[x<<1], mx[x<<1|1]);
}
void build(int x,int l,int r){
    if(l==r){
        //
        return;
    }
    int mid = (l+r) >> 1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    pushup(x);
}
void update(int x,int l,int r,int ql,int qr,long long v){
    if (ql <= l && qr >= r){
        mx[x] += v;
        lz[x] += v;
        return ;
    }
    pushdown(x);
    int mid = (l+r) >> 1;
    if(ql <= mid){
        update(x<<1, l, mid, ql, qr, v);
    }
    if(qr > mid){
        update(x<<1|1, mid + 1, r, ql, qr, v);
    }
    pushup(x);
}
long long query(int x,int l,int r,int ql,int qr){
    if (ql <= l && qr >= r){
        return mx[x];
    }
    pushdown(x);
    int mid = (l+r) >> 1;
    long long mx = -1e18;
    if(ql <= mid){
        mx = max(mx, query(x<<1,l,mid,ql,qr));
    }
    if(qr > mid){
        mx = max(mx, query(x<<1|1,mid+1,r,ql,qr));
    }
    return mx;
}
int main() {
    // Segment Tree Range add, Range max
}