-
Notifications
You must be signed in to change notification settings - Fork 2
/
increment-update-query-sum.cpp
76 lines (66 loc) · 1.64 KB
/
increment-update-query-sum.cpp
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
using q_node = long long;
using l_node = long long;
using u_node = long long;
struct LazySegTree {
int n, lg;
vector<q_node> st;
vector<l_node> lazy;
LazySegTree (int _n) : n(_n), lg(ceil(log2(n))), st(n<<1), lazy(n<<1) {
}
/* OPTIONAL
you can just build empty and
make n updates
*/
LazySegTree (const vector<q_node> &v) : n((int)v.size()), lg(ceil(log2(n))), st(n<<1), lazy(n<<1) {
for (int i = 0; i < n; i++) st[n+i] = v[i];
for (int i = n-1; i; i--) st[i] = combine(st[i<<1], st[i<<1|1]);
for (int i = 0; i < n<<1; i++) lazy[i] = l_node();
}
/*
how to combine two query nodes
*/
q_node combine(q_node a, q_node b) {
return a+b;
}
/*
how to apply the lazy _x_ to the node
at position _p_
*/
void apply(int p, l_node x, int sz, bool prop=1) {
st[p] += x*sz;
if (prop and p < n) lazy[p] += x;
}
void prop(int p) {
int sz = 1 << (lg-1);
for (int s = lg; s; s--, sz >>= 1) {
int i = p >> s;
if (lazy[i] != l_node()) {
apply(i<<1, lazy[i], sz);
apply(i<<1|1, lazy[i], sz);
lazy[i] = l_node();
}
}
}
void fixup(int p) {
for (int sz = 2; p >>= 1; sz <<= 1) {
st[p] = combine(st[p<<1], st[p<<1|1]);
apply(p, lazy[p], sz, 0);
}
}
q_node query(int a, int b) {
q_node ret = q_node();
for (prop(a+=n), prop(b+=n); a <= b; ++a>>=1, --b>>=1) {
if (a&1) ret = combine(ret, st[a]);
if (!(b&1)) ret = combine(ret, st[b]);
}
return ret;
}
void update(int l, int r, u_node x) {
int lo = l += n, ro = r += n, sz = 1;
for (; l <= r; ++l>>=1, (--r)>>=1, sz <<= 1) {
if (l&1) apply(l, x, sz);
if (!(r&1)) apply(r, x, sz);
}
fixup(lo), fixup(ro);
}
};