dynamic lazy segment tree¶
ソースコード¶
1#include <iostream>
2#include <cassert>
3#include <memory>
4
5#include "titan_cpplib/others/print.cpp"
6using namespace std;
7
8// DynamicLazySegmentTree
9namespace titan23 {
10
11 /**
12 * @brief `[0, u)` の列を管理する、必要なところだけ作る遅延セグ木
13 *
14 * - apply / set : `O(logu)` time, `O(logu)` space
15 *
16 * - prod / get : `O(logu)` time, `O(1)` space
17 *
18 * @tparam IndexType 添え字を表すインデックス long long を推奨 和がオーバーフローしないことが条件かな
19 * @tparam T モノイドの型
20 * @tparam (*op)(T, T) モノイドの2項演算
21 * @tparam (*e)() モノイドの単位元
22 * @tparam F 作用素の型
23 * @tparam (*mapping)(F, T) 遅延セグ木のアレ
24 * @tparam (*composition)(F, F) 遅延セグ木のアレ
25 * @tparam (*id)() 遅延セグ木のアレ
26 * @tparam (*pow)(T, IndexType) T=op(T,T)をk回繰り返した結果を返す関数
27 */
28 template <class IndexType,
29 class T,
30 T (*op)(T, T),
31 T (*e)(),
32 class F,
33 T (*mapping)(F, T),
34 F (*composition)(F, F),
35 F (*id)(),
36 T (*pow)(T, IndexType)>
37 class DynamicLazySegmentTree {
38 private:
39 static int bit_length(long long x) {
40 return x == 0 ? 0 : 64 - __builtin_clzll(x);
41 }
42
43 struct Node;
44 using NodePtr = Node*;
45 // using NodePtr = shared_ptr<Node>;
46 NodePtr root;
47 IndexType u;
48
49 struct Node {
50 NodePtr left, right;
51 IndexType l, r;
52 T key, data; // 子がないとき、data=pow(key, r-l)が成り立つ
53 F lazy;
54
55 Node() {}
56
57 Node(IndexType l, IndexType r, T key) :
58 left(nullptr), right(nullptr),
59 l(l), r(r),
60 key(key), data(pow(key, r-l)) {
61 // key(key), data(r-l == 1 ? key : pow(key, r-l)) {
62 assert(l < r);
63 }
64
65 bool is_leaf() const {
66 return this->r - this->l == 1;
67 }
68
69 void apply(const F f) {
70 if (f == id()) return;
71 this->key = mapping(f, this->key);
72 this->data = mapping(f, this->data);
73 if (!is_leaf()) this->lazy = composition(f, this->lazy);
74 }
75
76 void propagate() {
77 if (is_leaf()) return;
78 if (this->left) {
79 this->left->apply(this->lazy);
80 } else {
81 this->left = new Node(l, mid(), this->key);
82 }
83 if (this->right) {
84 this->right->apply(this->lazy);
85 } else {
86 this->right = new Node(mid(), r, this->key);
87 }
88 this->lazy = id();
89 }
90
91 void update() {
92 if (this->left) {
93 this->data = this->left->data;
94 } else {
95 this->data = e();
96 }
97 if (this->right) {
98 this->data = op(this->data, this->right->data);
99 }
100 }
101
102 IndexType mid() const {
103 return (this->l + this->r) / 2;
104 }
105 };
106
107 private:
108 T inner_prod(NodePtr node, const IndexType l, const IndexType r) {
109 if (!node || l >= r || r <= node->l || node->r <= l) return e();
110 if (l <= node->l && node->r <= r) return node->data;
111 if ((!node->left) && (!node->right)) return pow(node->key, r - l);
112 node->propagate();
113 return op(
114 inner_prod(node->left, l, min(r, node->mid())),
115 inner_prod(node->right, max(l, node->mid()), r)
116 );
117 }
118
119 T inner_prod2(NodePtr node, const IndexType l, const IndexType r, const F f) const {
120 cerr << PRINT_RED << "titan_cpplib-Error: this method has not been impremented yet.\n";
121 cerr << "Do not use prod2(), use prod()." << PRINT_NONE << endl;
122 assert(false); // NotImeprementedError
123 // if (!node || l >= r || r <= node->l || node->r <= l) return e();
124 // if (l <= node->l && node->r <= r) return mapping(f, node->data);
125 // if ((!node->left) && (!node->right)) return mapping(f, pow(node->key, r - l));
126 // return op(
127 // mapping(f, inner_prod2(node->left, l, min(r, node->mid()), composition(f, node->lazy))),
128 // mapping(f, inner_prod2(node->right, max(l, node->mid()), r, composition(f, node->lazy)))
129 // );
130 }
131
132 void inner_apply(NodePtr node, IndexType l, IndexType r, F f) {
133 if (!node || l >= r || r <= node->l || node->r <= l) return;
134 if (l <= node->l && node->r <= r) {
135 node->apply(f);
136 return;
137 }
138 node->propagate();
139 inner_apply(node->left, l, min(r, node->mid()), f);
140 inner_apply(node->right, max(l, node->mid()), r, f);
141 node->update();
142 }
143
144 void inner_set(NodePtr node, IndexType k, T val) {
145 assert(node);
146 if (node->is_leaf()) {
147 assert(node->l == k && node->r == k+1);
148 node->key = val;
149 node->data = val;
150 return;
151 }
152 node->propagate();
153 if (k < node->mid()) {
154 inner_set(node->left, k, val);
155 } else {
156 inner_set(node->right, k, val);
157 }
158 node->update();
159 }
160
161 T inner_get(NodePtr node, IndexType k) {
162 assert(node);
163 while (true) {
164 if (node->is_leaf()) {
165 assert(node->l == k && node->r == k+1);
166 return node->key;
167 }
168 if (k < node->mid()) {
169 if (!node->left) return node->key;
170 node->propagate();
171 node = node->left;
172 } else {
173 if (!node->right) return node->key;
174 node->propagate();
175 node = node->right;
176 }
177 }
178 }
179
180 public:
181
182 DynamicLazySegmentTree() : root(nullptr), u(0) {}
183
184 //! 初期値 `e()` , `[0, u)` の区間を管理する `DynamicLazySegmentTree` を作成する
185 DynamicLazySegmentTree(const IndexType u_) {
186 assert(u_ > 0);
187 this->u = (IndexType)1 << bit_length(u_);
188 this->root = new Node(0, this->u, e());
189 }
190
191 //! 初期値 `init` , `[0, u)` の区間を管理する `DynamicLazySegmentTree` を作成する
192 DynamicLazySegmentTree(const IndexType u_, const T init) {
193 assert(u_ > 0);
194 this->u = (IndexType)1 << bit_length(u_);
195 this->root = new Node(0, this->u, init);
196 }
197
198 //! `[l, r)` の集約値を返す / `O(logu)` time, `O(logu)` space
199 T prod(IndexType l, IndexType r) {
200 assert(0 <= l && l <= r && r <= u);
201 return inner_prod(this->root, l, r);
202 }
203
204 //! `[l, r)` の集約値を返す / `O(logu)` time, `O(1)` space
205 T prod2(IndexType l, IndexType r) const {
206 assert(0 <= l && l <= r && r <= u);
207 return inner_prod2(this->root, l, r, id());
208 }
209
210 //! `[l, r)` に `f` を作用させる / `O(logu)` time, `O(logu)` space
211 void apply(IndexType l, IndexType r, F f) {
212 assert(0 <= l && l <= r && r <= u);
213 inner_apply(this->root, l, r, f);
214 }
215
216 //! `k` 番目の値を取得する / `O(logu)` time, `O(1)` space
217 T get(IndexType k) {
218 return inner_get(this->root, k);
219 }
220
221 //! `k` 番目の値を `val` に更新する / `O(logu)` time, `O(logu)` space
222 void set(IndexType k, T val) {
223 assert(0 <= k && k < u);
224 inner_set(this->root, k, val);
225 }
226
227 //! 適当に表示する
228 void print() {
229 for (IndexType i = 0; i < u; ++id) {
230 cout << get(i) << ", ";
231 }
232 cout << endl;
233 }
234 };
235} // namespace titan23
仕様¶
Warning
doxygenfile: Cannot find file “titan_cpplib/data_structures/dynamic_lazy_segment_tree.cpp