lazy segment tree¶
ソースコード¶
1#include <vector>
2#include <cassert>
3using namespace std;
4
5// LazySegmentTree
6namespace titan23 {
7
8 template <class T,
9 T (*op)(T, T),
10 T (*e)(),
11 class F,
12 T (*mapping)(F, T),
13 F (*composition)(F, F),
14 F (*id)()>
15 class LazySegmentTree {
16 private:
17 int n, log, size;
18 vector<T> data;
19 vector<F> lazy;
20
21 static int bit_length(const int x) {
22 if (x == 0) return 0;
23 return 32 - __builtin_clz(x);
24 }
25
26 void update(int k) {
27 data[k] = op(data[k << 1], data[k << 1 | 1]);
28 }
29
30 void all_apply(int k, F f) {
31 data[k] = mapping(f, data[k]);
32 if (k >= size) return;
33 lazy[k] = composition(f, lazy[k]);
34 }
35
36 void propagate(int k) {
37 if (lazy[k] == id()) return;
38 all_apply(k << 1, lazy[k]);
39 all_apply(k << 1 | 1, lazy[k]);
40 lazy[k] = id();
41 }
42
43 void upper_propagate(int l, int r) {
44 for (int i = log; i > 0; --i) {
45 if ((l>>i<<i) != l) {
46 propagate(l >> i);
47 }
48 if (((r>>i<<i) != r) && ( ((l>>i) != ((r-1)>>i)) || ((l>>i<<i) == l) )) {
49 propagate((r-1) >> i);
50 }
51 }
52 }
53
54 public:
55 LazySegmentTree() : n(0), log(0), size(0) {}
56 LazySegmentTree(int n) {
57 this->n = n;
58 this->log = bit_length(n-1);
59 this->size = 1 << log;
60 data.resize(this->size<<1, e());
61 lazy.resize(this->size, id());
62 }
63
64 LazySegmentTree(const vector<T> a) {
65 this->n = a.size();
66 this->log = bit_length(n-1);
67 this->size = 1 << log;
68 data.resize(this->size<<1, e());
69 for (int i = size; i < size+n; ++i) {
70 data[i] = a[i-size];
71 }
72 for (int i = size-1; i > 0; --i) {
73 data[i] = op(data[i<<1], data[i<<1|1]);
74 }
75 lazy.resize(this->size, id());
76 }
77
78 void apply_point(int k, F f) {
79 k += size;
80 for (int i = log; i > 0; --i) {
81 propagate(k >> i);
82 }
83 data[k] = mapping(f, data[k]);
84 for (int i = 1; i <= log; ++i) {
85 update(k >> i);
86 }
87 }
88
89 void apply(int l, int r, F f) {
90 if (l == r || f == id()) return;
91 l += size;
92 r += size;
93 upper_propagate(l, r);
94 int l2 = l, r2 = r;
95 while (l < r) {
96 if (l & 1) {
97 all_apply(l, f);
98 l += 1;
99 }
100 if (r & 1) {
101 all_apply(r ^ 1, f);
102 }
103 l >>= 1;
104 r >>= 1;
105 };
106 int l3 = l2, r3 = r2 - 1;
107 for (int i = 1; i <= log; ++i) {
108 l3 >>= 1;
109 r3 >>= 1;
110 if ((l3 << i) != l2) {
111 update(l3);
112 }
113 if ((((l3 << i) == l2) || (l3 != r3)) && ((r2>>i<<i) != r2)) {
114 update(r3);
115 }
116 }
117 }
118
119 void all_apply(F f) {
120 lazy[1] = f == id() ? f : composition(f, lazy[1]);
121 }
122
123 T prod(int l, int r) {
124 if (l == r) return e();
125 l += size;
126 r += size;
127 upper_propagate(l, r);
128 T lres = e(), rres = e();
129 while (l < r) {
130 if (l & 1) lres = op(lres, data[l++]);
131 if (r & 1) rres = op(data[r^1], rres);
132 l >>= 1;
133 r >>= 1;
134 }
135 return op(lres, rres);
136 }
137
138 T all_prod() const {
139 return data[1];
140 }
141
142 T get(int k) {
143 k += size;
144 for (int i = log; i > 0; --i) {
145 propagate(k >> i);
146 }
147 return data[k];
148 }
149
150 void set(int k, T v) {
151 k += size;
152 for (int i = log; i > 0; --i) {
153 propagate(k >> i);
154 }
155 data[k] = v;
156 for (int i = 1; i <= log; ++i) {
157 update(k >> i);
158 }
159 }
160
161 template<typename Func>
162 int max_right(int l, Func f) {
163 assert(0 <= l <= n);
164 if (l == size) return n;
165 l += size;
166 for (int i = log; i > 0; --i) {
167 propagate(l>>i);
168 }
169 T s = e();
170 while (true) {
171 while (l & 1 == 0) {
172 l >>= 1;
173 }
174 if (!f(op(s, data[l]))) {
175 while (l < size) {
176 propagate(l);
177 l <<= 1;
178 if (f(op(s, data[l]))) {
179 s = op(s, data[l]);
180 l |= 1;
181 }
182 }
183 return l - size;
184 }
185 s = op(s, data[l]);
186 l++;
187 if (l & (-l) == l) break;
188 }
189 return n;
190 }
191
192 template<typename Func>
193 int min_left(int r, Func f) {
194 assert(0 <= r <= n);
195 if (r == 0) return 0;
196 r += size;
197 for (int i = log; i > 0; --i) {
198 propagate((r - 1) >> i);
199 }
200 T s = e();
201 while (true) {
202 r -= 1;
203 while ((r > 1) && (r & 1)) {
204 r >>= 1;
205 }
206 if (!f(op(data[r], s))) {
207 while (r < size) {
208 propagate(r);
209 r = r << 1 | 1;
210 if (f(op(data[r], s))) {
211 s = op(data[r], s);
212 r ^= 1;
213 }
214 }
215 return r + 1 - size;
216 }
217 s = op(data[r], s);
218 if (r & (-r) == r) break;
219 }
220 return 0;
221 }
222
223 vector<T> tovector() {
224 for (int i = 1; i < size; ++i) {
225 propagate(i);
226 }
227 vector<T> res(data.begin()+size, data.begin()+size+n);
228 return res;
229 }
230 };
231} // namespace titan23
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/lazy_segment_tree.cpp