動的な Segment Tree のテクニック
区間に(初期値を)代入
普通は区間代入といえば遅延伝搬を使いますが, 遅延なしでも初期値を代入する場合は実は簡単にできます.
方法は, 代入したい区間の各部分木を null に置き換えるだけです.
一応もう少し工夫すると, 区間代入にも一般化できます.
2つの列の同じ区間 [l, r] を swap
これは一見, 平衡二分木の split 操作が必要そうに見えます.
しかしよく考えると, 代入したい区間の各部分木を swap するとできます.
永続化すればコピー操作にもできますね.
bool値の区間 flip
上記の区間 swap を使うと, 遅延伝搬なしでbool値の区間 flip 操作が可能になります.
やり方は, 元の列と各値が反転した列の2つの列を持っておいて, 反転操作ではその区間でswapするとできます.
使える問題：AOJ RUPC2017 Day3 E
さらに, 整数に対してビット独立にこれを使うと区間XORができることもあります.
使える問題：HackerRank HourRank28 C
空間計算量を O(NlogX) から O(N) に減らす
基数木(Radix Tree/Patricia Trie)でも同等のことができますが, こっちの方が若干実装が楽そう(?)
点更新の場合
通常は null のノードにたどり着いても, 葉までノードを作りながら降りていきますが, これをすぐにやめるようにします.
各ノードには持たせるものは, 位置とその位置の値と部分木全体の値です.
更新時には更新される位置を持ったノードが見つかるまで降りていって更新しますが, 見つからなければ新しくノードを作成します.
取得クエリでは普通と同じように降りていきますが, 途中のノードも目的の区間に含まれていれば答えと合わせます.
あと, ノードの重複を避けるために適当な条件を満たすようにしておきましょう.
この方法を使うと平均的に深さが減ったり, メモリ確保の回数も減るので定数倍が速くなることが多い気がします.
実装例
template <typename M> // Mは 型type, 単位元id(), 演算op() を持つモノイド class dynamic_segment_tree { using T = typename M::type; struct node { int pos; T val, all; node *l, *r; node(int p, T v) : pos(p), val(v), all(v), l(nullptr), r(nullptr) {} }; private: const int n; node *root; public: dynamic_segment_tree(int n_) : n(1 << (int)ceil(log2(n_))), root(nullptr) {} void update(int p, T val) { root = change(root, p, val, 0, n); } T find(int l, int r) { return get(l, r, root, 0, n); } private: T value(node *t) { return t ? t->all : M::id(); } T get(int l, int r, node* t, int lb, int ub) { if (!t || ub <= l || r <= lb) return M::id(); if (l <= lb && ub <= r) return t->all; int c = (lb + ub) / 2; T res = get(l, r, t->l, lb, c); if (l <= t->pos && t->pos < r) res = M::op(res, t->val); return M::op(res, get(l, r, t->r, c, ub)); } node *change(node* t, int p, T val, int lb, int ub) { if (!t) return new node(p, val); if (t->pos == p) { t->val = val; t->all = M::op(value(t->l), M::op(t->val, value(t->r))); return t; } int c = (lb + ub) / 2; if (p < c) { if (p > t->pos) swap(p, t->pos), swap(val, t->val); t->l = change(t->l, p, val, lb, c); } else { if (p < t->pos) swap(p, t->pos), swap(val, t->val); t->r = change(t->r, p, val, c, ub); } t->all = M::op(value(t->l), M::op(t->val, value(t->r))); return t; } };
使える問題：AtCoder KUPC2018 M
(↑この問題の想定解はこのテクなんですが, 使わなくても通っちゃうみたいです. 悲しいね.)
