/
segTree.cc
executable file
·291 lines (260 loc) · 7.62 KB
/
segTree.cc
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
/*
Segment Tree (non-recursive version; including laziness)
See https://yamate11.github.io/blog/posts/2023/12-03-segment-tree-lib/
*/
//////////////////////////////////////////////////////////////////////
// See help of libins command for dependency spec syntax.
// @@ !! BEGIN(f:<<) ---- segTree.cc
// It seems that we should keep the size power of two,
// considering the binary search.
pair<int, int> segtree_range_of_node(int ht, unsigned i) {
unsigned m = bit_floor(i);
unsigned w = ht + 1 - bit_width(i);
int lo = (i ^ m) << w;
int hi = lo + (1LL << w);
return make_pair(lo, hi);
}
vector<int> segtree_nodes_for_range(int ht, unsigned lo, unsigned hi) {
vector<int> left;
vector<int> right;
lo = (1 << ht) + lo;
hi = (1 << ht) + hi - 1;
while (lo <= hi) {
if (lo == hi) {
left.push_back(lo);
break;
}
if (lo & 1) {
left.push_back(lo);
lo++;
}
if (not (hi & 1)) {
right.push_back(hi);
hi--;
}
lo >>= 1;
hi >>= 1;
}
while (not right.empty()) {
left.push_back(right.back());
right.pop_back();
}
return left;
}
template <typename DAT, typename OP,
typename ADD_t, typename COMP_t, typename APPL_t, bool lazy>
struct GenSegTree {
using GST = GenSegTree<DAT, OP, ADD_t, COMP_t, APPL_t, lazy>;
int orig_size; // size of initdat
int size; // power of two; >= 2
int height; // size = 1 << height;
vector<DAT> node; // vector of size 2*size.
// 0 : unused
// 1 ... size-1 : interval
// size ... 2*size-1 : leaf
vector<OP> susp; // vector of size size.
// suspended operation FOR CHILDREN
// (already applied to this node)
DAT unit_dat;
OP unit_op;
ADD_t add;
COMP_t comp;
APPL_t appl;
GenSegTree() {}
GenSegTree(DAT unit_dat_, OP unit_op_, ADD_t add_, COMP_t comp_, APPL_t appl_,
const vector<DAT>& initdat = vector<DAT>())
: unit_dat(unit_dat_), unit_op(unit_op_),
add(add_), comp(comp_), appl(appl_) { set_data(initdat); }
void set_data(const vector<DAT>& initdat) {
orig_size = initdat.size();
if (initdat.size() <= 1) height = 0;
else height = sizeof(int) * 8 - __builtin_clz(initdat.size() - 1);
size = 1 << height;
node.resize(2*size, unit_dat);
for (int i = 0; i < (int)initdat.size(); i++) node[size + i] = initdat[i];
for (int t = size - 1; t >= 1; t--) node[t] = add(node[t<<1|0], node[t<<1|1]);
susp.resize(size, unit_op);
}
void child_updated_sub(int t) {
node[t] = appl(susp[t], add(node[t<<1|0], node[t<<1|1]));
}
void child_updated(int l, int r) {
r--;
while (l > 1) {
l >>= 1;
r >>= 1;
child_updated_sub(l);
if (l < r) child_updated_sub(r);
}
}
void node_op(int i, OP f) {
node[i] = appl(f, node[i]);
if (i < size) susp[i] = comp(f, susp[i]);
}
// Note that susp[i] HAS ALREADY BEEN APPLIED TO node[i].
// When push_one(i) is called, susp[j] is updated (for j : i's child) and it is applied to node[j].
void push_one(int i) {
node_op(i<<1|0, susp[i]);
node_op(i<<1|1, susp[i]);
susp[i] = unit_op;
}
void push_upto(int l, int r) {
for (int s = height; s >= 1; s--) {
int lz = l >> s;
int rz = (r-1) >> s;
push_one(lz);
if (lz < rz) push_one(rz);
}
}
DAT query(int l, int r) {
if (l >= r) return unit_dat;
DAT ret_l = unit_dat;
DAT ret_r = unit_dat;
l += size;
r += size;
if constexpr(lazy) push_upto(l, r);
while (l < r) {
if (l & 1) {
ret_l = add(ret_l, node[l]);
l++;
}
if (r & 1) {
ret_r = add(node[r-1], ret_r);
}
l >>= 1;
r >>= 1;
}
DAT ret = add(ret_l, ret_r);
return ret;
}
const DAT& get_single(int i) {
if constexpr(lazy) push_upto(size + i, size + i + 1);
return node[size + i];
}
void set_single(int i, const DAT& t) {
ll x = size + i;
if constexpr(lazy) push_upto(x, x + 1);
node[x] = t;
for (x >>= 1; x >= 1; x >>= 1) node[x] = add(node[x<<1|0], node[x<<1|1]);
}
// obsolete
template<bool xx = lazy> enable_if_t<! xx> update(int i, DAT t) {
ll x = size + i;
node[x] = t;
for (x >>= 1; x >= 1; x >>= 1) node[x] = add(node[x<<1|0], node[x<<1|1]);
}
template<bool xx = lazy> enable_if_t<xx> update(int l, int r, const OP& f) {
if (l >= r) return;
l += size;
r += size;
push_upto(l, r);
int l0 = l, r0 = r;
while (l < r) {
if (l & 1) {
node_op(l, f);
l++;
}
if (r & 1) {
node_op(r-1, f);
}
l >>= 1;
r >>= 1;
}
child_updated(l0, r0);
}
pair<int, int> range_of_node(unsigned i) { return segtree_range_of_node(height, i); }
vector<int> nodes_for_range(unsigned lo, unsigned hi) { return segtree_nodes_for_range(height, lo, hi); }
friend ostream& operator<<(ostream& os, GenSegTree& st) {
os << '[';
for (int i = 0; i < st.orig_size; i++) {
if (i > 0) os << ", ";
os << st.get_single(i);
}
os << ']';
return os;
}
int binsearch_r_until(const auto& check, int l) {
// DLOGKL("in: binsearch_r_until", l);
if (not check(unit_dat)) return l - 1;
if (l == orig_size) return l;
DAT val = unit_dat;
int x = l + size;
if constexpr(lazy) push_upto(x, x + 1);
while (true) {
if (x & 1) {
DAT t = add(val, node[x]);
if (not check(t)) break;
val = t;
x++;
if (__builtin_popcountll(x) == 1) return orig_size;
}
x >>= 1;
// DLOGKL("1: ", x, val);
}
while (x < size) {
if constexpr(lazy) push_one(x);
x <<= 1;
DAT t = add(val, node[x]);
if (check(t)) {
x++;
val = t;
}
// DLOGKL("2: ", x, val);
}
// DLOGKL("3: ", x - size, orig_size);
return min(x - size, orig_size);
}
int binsearch_r_from(const auto& check, int l) {
return binsearch_r_until([&](DAT x) { return not check(x); }, l) + 1;
}
int binsearch_l_until(const auto& check, int r) {
if (not check(unit_dat)) return r + 1;
if (r == 0) return 0;
DAT val = unit_dat;
int x = r + size;
if (x == 2 * size) {
if (check(node[1])) return 0;
x = 1;
}else {
if constexpr(lazy) push_upto(x - 1, x);
while (true) {
if (x & 1) {
x--;
DAT t = add(node[x], val);
if (not check(t)) break;
val = t;
if (__builtin_popcountll(x) == 1) return 0;
}
x >>= 1;
}
}
while (x < size) {
if constexpr(lazy) push_one(x);
x = x << 1 | 1;
DAT t = add(node[x], val);
if (check(t)) {
val = t;
x--;
}
}
return x + 1 - size;
}
int binsearch_l_from(const auto& check, int r) {
return binsearch_l_until([&](DAT x) { return not check(x); }, r) - 1;
}
};
template<typename DAT, typename OP>
auto make_seg_tree_lazy(DAT unit_dat, OP unit_op, auto add, auto comp, auto appl,
const vector<DAT>& initdat = vector<DAT>()) {
using ret_t = GenSegTree<DAT, OP, decltype(add), decltype(comp), decltype(appl), true>;
return ret_t(unit_dat, unit_op, add, comp, appl, initdat);
}
void* dummy_comp(void* x, void* y) { return nullptr; }
template<typename DAT>
DAT dummy_appl(void* x, const DAT& y) { return y; }
template<typename DAT>
auto make_seg_tree(DAT unit_dat, auto add, const vector<DAT>& initdat = vector<DAT>()) {
using ret_t = GenSegTree<DAT, void*, decltype(add), void* (*)(void*, void*), DAT (*)(void*, const DAT&), false>;
return ret_t(unit_dat, nullptr, add, dummy_comp, dummy_appl<DAT>, initdat);
}
// @@ !! END() ---- segTree.cc