-
Notifications
You must be signed in to change notification settings - Fork 0
/
segment_tree.cpp
88 lines (73 loc) · 1.92 KB
/
segment_tree.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
77
78
79
80
81
82
83
84
85
86
87
88
#include <vector>
#include <iostream>
using namespace std;
template<typename T>
class SegTree
{
public:
SegTree(size_t max_range)
{
size_t p = 1;
while(p < max_range) p*=2;
this->max_range = p;
vec.resize(p*2+5, 0);
lazy.resize(p*2+5, 0);
}
void update_interval(size_t l, size_t r, T val)
{
update_interval_rec(l,r,1,max_range,1,val);
}
T query(size_t l, size_t r)
{
return query_rec(l,r,1,max_range,1);
}
private:
void propagate(size_t len, size_t node)
{
if(lazy[node])
{
vec[node] += static_cast<T>(len)*lazy[node];
if(2*node < lazy.size())
lazy[2*node] += lazy[node];
if(2*node+1 < lazy.size())
lazy[2*node+1] += lazy[node];
lazy[node] = 0;
}
}
T query_rec(size_t l, size_t r, size_t start, size_t end, size_t node)
{
propagate(end-start+1,node);
if(l <= start and end <= r)
{
return vec[node];
}
if(l > end or r < start)
return 0;
size_t m = (start+end)/2;
T left_res = query_rec(l, r, start, m, node*2);
T right_res = query_rec(l, r, m+1, end, node*2+1);
return left_res + right_res;
}
void update_interval_rec(size_t l, size_t r, size_t start, size_t end, size_t node, T val)
{
propagate(end-start+1,node);
if(l <= start and end <= r)
{
lazy[node] += val;
propagate(end-start+1,node);
return;
}
if(l > end or r < start)
return;
size_t m = (start+end)/2;
update_interval_rec(l, r, start, m, node*2, val);
update_interval_rec(l, r, m+1, end, node*2+1, val);
vec[node] = vec[2*node]+vec[2*node+1];
}
size_t max_range;
vector<T> lazy;
vector<T> vec;
};
int main()
{
}