/
dynamicsegmenttree.cpp
115 lines (88 loc) · 2.45 KB
/
dynamicsegmenttree.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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
template <typename T>
struct Segtree{
struct SegNode;
struct SegNode{
T val;
SegNode* l;
SegNode* r;
SegNode(T val) : val(val), l(nullptr), r(nullptr){}
};
i64 n;
function<T(T, T)> f;
T op;
SegNode* root;
Segtree(int n_, function<T(T, T)> f, T op) : f(f), op(op){
for(n = 1; n < n_; n <<= 1);
root = new SegNode(op);
}
SegNode* getl(SegNode* node, T val){
return node->l == nullptr ? node->l = new SegNode(val) : node->l;
}
SegNode* getr(SegNode* node, T val){
return node->r == nullptr ? node->r = new SegNode(val) : node->r;
}
void eval(SegNode* node){
node->val = f(node->l == nullptr ? op : node->l->val, node->r == nullptr ? op : node->r->val);
}
void set(i64 x, T val){
assert(0 <= x && x < n);
SegNode* node = root;
stack<SegNode*> nodes;
i64 l = 0, r = n;
while(r - l > 1){
nodes.push(node);
i64 mid = (l + r) >> 1;
if(x < mid){
node = getl(node, x);
r = mid;
}else{
node = getr(node, x);
l = mid;
}
}
node->val = val;
while(!nodes.empty()){
eval(nodes.top());
nodes.pop();
}
}
void update(i64 x, T val){
assert(0 <= x && x < n);
SegNode* node = root;
stack<SegNode*> nodes;
i64 l = 0, r = n;
while(r - l > 1){
nodes.push(node);
i64 mid = (l + r) >> 1;
if(x < mid){
node = getl(node, x);
r = mid;
}else{
node = getr(node, x);
l = mid;
}
}
node->val = f(node->val, val);
while(!nodes.empty()){
eval(nodes.top());
nodes.pop();
}
}
T get(i64 x, i64 y, SegNode* node = nullptr, i64 l = 0, i64 r = 0){
if(node == nullptr){
node = root;
r = n;
}
if(x <= l && r <= y)
return node->val;
if(r <= x || y <= l)
return op;
T val_l = op, val_r = op;
i64 mid = (l + r) >> 1;
if(node->l != nullptr)
val_l = f(val_l, get(x, y, node->l, l, mid));
if(node->r != nullptr)
val_r = f(get(x, y, node->r, mid, r), val_r);
return f(val_l, val_r);
}
};