[Link] https://www.acmicpc.net/problem/10999
Lazy propagation with non recursive segment tree. There was no code sample of using lazy propagation with recursive segment tree so I’ll share this code. Hope this help some one.
*Not to using scanf and cin when ios_base::sync_with_stdio(0)(turn off the sync to stdio);
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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1024 * 1024;
ll seg[2 * N];
ll lazy[2 * N];
int n;
int segH = 0;
ll arr[N];
void init() {
for(int i = N - 1; i > 0; i--) seg[i] = seg[i << 1] + seg[i << 1 | 1];
int i = N;
while(i > 0) i>>=1, segH++;
}
void apply(int idx) {
seg[idx] += lazy[idx];
if(idx < N) {
lazy[idx<<1] += lazy[idx]>>1;
lazy[idx<<1|1] += lazy[idx]>>1;
}
lazy[idx] = 0l;
}
void propagate(int idx) {
int nn = idx, log = 0;
while(nn > 0) nn>>=1, log++;
for(int i = segH; i >= 0; i--) {
int index = idx >> i;
if(lazy[index] != 0l) {
apply(index);
}
}
}
void updateParent(int idx, ll add) {
propagate(idx);
if(idx < N) lazy[idx]+=add;
else seg[idx] += add;
while(idx > 1) idx>>=1, seg[idx]+=add;
}
void update(int l, int r, ll add) {
for(l+=N, r+=N; l < r; l>>=1, r>>=1, add<<=1) {
if(l & 1) updateParent(l++, add);
if(r & 1) updateParent(--r, add);
}
}
ll query(int l, int r) {
ll sum = 0l;
for(l+=N, r+=N; l<r; l>>=1, r>>=1) {
if(l & 1) {
propagate(l);
sum+=seg[l++];
}
if(r & 1) {
propagate(--r);
sum+=seg[r];
}
}
return sum;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int m, k, mk;
cin >> n >> m >> k;
mk = m + k;
for(int i = 0; i < n; i++) cin >> seg[N + i];
init();
for(int i = 0; i < m + k; i++) {
int a, b, c;
cin >> a >> b >> c;
if(a == 1) {
ll d; cin >> d;
update(b - 1, c, d);
} else cout << query(b - 1, c) << '\n';
}
return 0;
}