-
Notifications
You must be signed in to change notification settings - Fork 0
/
SegmentTreeTopDown.h
40 lines (32 loc) · 1.21 KB
/
SegmentTreeTopDown.h
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
#include <vector>
#include <limits>
class SegmentTreeTopDown {
private:
std::vector<int> data;
int n;
public:
SegmentTreeTopDown(int n) {
this->n = n;
data.assign(4*n, 0);
}
void update(int node, int lower_bound, int upper_bound, int idx, int val) {
if (lower_bound > upper_bound || lower_bound > idx || upper_bound < idx)
return;
if (lower_bound == upper_bound) { // leave node
data[node] = val;
return;
}
update(node<<1, lower_bound, (lower_bound+upper_bound)>>1, idx, val);
update(node<<1|1, ((lower_bound+upper_bound)>>1)+1, upper_bound, idx, val);
data[node] = std::min(data[node<<1], data[node<<1|1]);
}
int query(int node, int lower_bound, int upper_bound, int l, int r) {
if (lower_bound > upper_bound || lower_bound > r || upper_bound < l)
return std::numeric_limits<int>::max();
if (lower_bound >= l && upper_bound <= r)
return data[node];
int q1 = query(node<<1, lower_bound, (lower_bound+upper_bound)>>1, l, r);
int q2 = query(node<<1|1, ((lower_bound+upper_bound)>>1)+1, upper_bound, l, r);
return std::min(q1, q2);
}
};