AlgorithmLibrary/LazyArray.cpp at master · bluecoffee8/AlgorithmLibrary · 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
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
102
103
104
105
106
107
108
109
110
/**
 * Author: Kevin Li
 * Lang: C++
 * Description: Array with quick range modifications using lazy propagation
 */

#include <iostream>
#include <vector>
using namespace std;

struct lazy_array {
    struct node {
        bool v;
        int val;
        int lazy;
        bool ch;
        int lch;
        node *l, *r;
        node () : v(false), val(0), lazy(0), ch(false), lch(0), l(0), r(0) {}
    };
    typedef node* tn;
    tn root;
    int n;
    lazy_array () {}
    lazy_array (int _n) : n(_n) {
        root = new node();
    }
    void ext(tn v) {
        if (!v->l) v->l = new node();
        if (!v->r) v->r = new node();
    }
    void push(tn v, int l, int r) {
        if (l == r) v->v = true;
        if (v->ch) {
            if (l == r) {
                v->val = v->lch;
            } else {
                ext(v);
                v->l->ch = true;
                v->r->ch = true;
                v->l->lch = v->lch;
                v->r->lch = v->lch;
            }
            v->lazy = 0;
            v->ch = false;
            v->lch = 0;
        } else if (v->lazy != 0) {
            if (l == r) {
                v->val += v->lazy;
            } else {
                ext(v);
                v->l->lazy += v->lazy;
                v->r->lazy += v->lazy;
            }
            v->lazy = 0;
        }
    }
    void build(tn v, int l, int r, vector<int> a) {
        if (l == r) {
            v->v = true;
            v->val = a[l];
        } else {
            ext(v);
            build(v->l,l,(l+r)/2,a);
            build(v->r,(l+r)/2+1,r,a);
        }
    }
    void augment(tn v, int l, int r, int L, int R, int val) {
        push(v,l,r);
        if (l > R || L > r) return;
        if (L <= l && r <= R) {
            if (v->ch) {
                v->lch += val;
            } else {
                v->lazy += val;
            }
        } else {
            ext(v);
            augment(v->l,l,(l+r)/2,L,R,val);
            augment(v->r,(l+r)/2+1,r,L,R,val);
        }
    }
    void change(tn v, int l, int r, int L, int R, int val) {
        push(v,l,r);
        if (l > R || L > r) return;
        if (L <= l && r <= R) {
            v->ch = true;
            v->lch = val;
            v->lazy = 0;
        } else {
            ext(v);
            change(v->l,l,(l+r)/2,L,R,val);
            change(v->r,(l+r)/2+1,r,L,R,val);
        }
    }
    int get(tn v, int l, int r, int i) {
        push(v,l,r);
        if (l == r) return v->val;
        ext(v);
        if (i <= (l+r)/2) {
            return get(v->l,l,(l+r)/2,i);
        } else {
            return get(v->r,(l+r)/2+1,r,i);
        }
    }
};

int main() {

}