-
Notifications
You must be signed in to change notification settings - Fork 753
/
Segment Tree NonRecursive.cpp
60 lines (51 loc) · 1.23 KB
/
Segment Tree NonRecursive.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
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n, a[N];
struct Node {
int sum;
Node() { sum = 0; }
Node(int val) { sum = val; }
};
struct ST {
int n;
Node *t;
ST(int _n) { n = _n; t = new Node[2 * n]; }
inline Node combine(Node l, Node r) {
Node res;
res.sum = l.sum + r.sum;
return res;
}
void build() {
for(int i = 0; i < n; i++) t[i + n] = Node(a[i+1]);
for(int i = n - 1; i > 0; --i) t[i] = combine(t[i << 1], t[i << 1 | 1]);
}
void upd(int p, int v) {
p--;
for (t[p += n] = Node(v); p >>= 1; ) t[p] = combine(t[p << 1], t[p << 1 | 1]);
}
Node query(int l, int r) {
--l;
bool f1 = 1, f2 = 1;
Node resl, resr;
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) resl = f1 ? t[l++] : combine(resl, t[l++]), f1 = 0;
if(r & 1) resr = f2 ? t[--r] : combine(t[--r], resr), f2 = 0;
}
if(f2) return resl;
if(f1) return resr;
return combine(resl, resr);
}
};
int32_t main() {
n = 3;
a[1] = 1;
a[2] = 2;
a[3] = 3;
ST t = ST(n);
t.build();
cout << t.query(1, 2).sum << '\n';
t.upd(2, 10);
cout << t.query(1, 3).sum << '\n';
return 0;
}