AtCoderLibrary Lazy-SegmentTree 基礎実装例集
色々実装してみたので、ここに置いておく
対象読者
- 十分な実装時間があれば簡単な機能をもった（例：範囲加算・範囲総和取得など）遅延セグメント木を実装できる
- ATLのlazy_segtreeを使う前に、自分で抽象化されていない簡単な遅延セグメント木を作ってみることを強くおすすめします。
- 抽象化遅延セグメント木特有の考察や、内部実装の理解を前提としたインターフェースが多い為です。
- AtCoderLibrary をコンテスト時間内で読んで分からなかった人向き
全部説明されていなかったら、それは自分の説明力不足です。すみません。
遅延セグメント木を使う上での注意
- 制限に注意。
- うっかり何でも出来ると勘違いしてしまいがちだが、前提を満たさない関数を実装すると、動かない。モノイドとか
- 適切に状態をもたせると、前提を満たす設計が出来るようになる場合がある。本記事では、その例を掲載。
- 遅延セグメント木より汎用性の高い配列型データ構造に平方分割があります。各クエリの計算量がO(sqrt(N))なので注意
- うっかり何でも出来ると勘違いしてしまいがちだが、前提を満たさない関数を実装すると、動かない。モノイドとか
practice
区間最大値更新・区間最大値取得
多分、一番簡単な例です。 コメントも入れてみた。
#include <bits/stdc++.h> using namespace std; #include <atcoder/segtree> #include <atcoder/lazysegtree> using namespace atcoder; #define LSEGTRAIT(t) t::S, t::op, t::e, t::F, t::mapping, t::composition, t::id struct lsegtrait{ using S = int; // apply の引数のようなもの // 今回は、最大値更新する値だけ struct F { int setter; }; // l から r までを op で順に演算した結果を計算したい // op(op(data_[l], data_[l+1]), data_[l+2] .... // 今回は、範囲全体の最大値を取りたいので、maxを使うだけ。 static S op(S l, S r) { return max(l, r); } // op の意味を成さない値。 // 今回は、opを最大値と定義しているので、 // e()を最小値として定義すれば、max(x, e()) == xが常に成り立つ // 0を最小値としてみた。 static S e() { return 0; } // apply の実装 // x をapplyの引数 f を使って変化させ、その結果を返す // Javscript の有名ライブラリ Redux での Reducer に該当しそう static S mapping(F f, S x) { return max(x, f.setter); } // apply の処理は「合成」出来なければならない // fを適用した後にgを適用することと同値の、Fを設計する。 // 今回の場合、fとgで大きい方だけを適用すれば、fを適用した後にgを適用することと同値になる。 static F composition(F f, F g) { return f.setter > g.setter ? f : g; } // 適用しても影響が無い apply を定義する // 今回は、「最小値で最大値更新する」applyが無影響。 static F id() { return F{0}; } lsegtrait() = delete; // インスタンス化は要らない }; int main() { int N; cin >> N; lazy_segtree<LSEGTRAIT(lsegtrait)> segment(N); while (true) { string cmd; cin >> cmd; if (cmd == "apply") { int begi, en, valu; cin >> begi >> en >> valu; segment.apply(begi, en, lsegtrait::F{valu}); cout << "apply[" << begi << "..." << en << ") <= " << valu << endl; } else if (cmd == "calc") { int begi, en; cin >> begi >> en; auto res = segment.prod(begi, en); cout << "calc [" << begi << "..." << en << ") => " << res << endl; } else break; } cout << "complete!" << endl; return 0; }
- 本当は継承を使って書きたかったのですが、traitをinjectする風味の実装にしています。
- 本番は、
#define LSEGTRAIT...からstruct lsegtrait{ .. };までをコピペして中身を改変すれば、楽です。
入出力例
// INPUT 5 calc 0 5 apply 0 2 9 calc 0 5 calc 3 5 apply 1 4 8 calc 0 2 calc 1 5 calc 3 5 calc 4 5 EOL // OUTPUT calc [0...5) => 0 apply[0...2) <= 9 calc [0...5) => 9 calc [3...5) => 0 apply[1...4) <= 8 calc [0...2) => 9 calc [1...5) => 9 calc [3...5) => 8 calc [4...5) => 0 complete!
simple
区間更新・区間最大値取得
区間を指定した値で置き換える実装を考える。
取得は、先程と同じ区間の最大値。
実行例は以下。
apply[2...4) <= 8 calc [0...5) => 8 calc [0...2) => 0 calc [4...5) => 0 apply[3...5) <= 9 calc [0...5) => 9 calc [0...3) => 8 calc [4...5) => 9 apply[0...3) <= 7 calc [0...2) => 7 calc [2...4) => 9 calc [4...5) => 9 complete!
先程と同様に S と F を次のように定義すると、lsegtrait::id の定義で詰むことになる。
struct lsegtrait{ using S = int; struct F { int setter; // S を setter で置き換える }; ...
任意のS に対して lsegtrait::mapping を適用しても影響がないような F が存在しないからである。
そこで、lsegtrait::id となるような F を無理やり作る。
struct lsegtrait{ using S = int; struct F { int setter; // S を setter で置き換える bool ignore = false; // ただし、このフラグが true の時は置き換えない }; ...
これで、id が存在するようになり、設計できるようになった。
struct lsegtrait{ using S = int; struct F { int setter; bool ignore = false; }; static S op(S l, S r) { return max(l, r); } static S e() { return 0; } static S mapping(F f, S x) { return f.ignore ? x : f.setter; } static F composition(F f, F g) { return g.ignore ? f : g; } static F id() { return F{0, true}; } lsegtrait() = delete; };
区間更新・区間総和取得
実行例は以下
apply[0...2) <= 3 calc [0...5) => 6 calc [0...3) => 6 calc [4...5) => 0 apply[3...5) <= 5 calc [0...5) => 16 calc [0...3) => 6 calc [2...3) => 0 calc [1...4) => 8 calc [3...5) => 10 complete!
先程の「区間更新・区間最大値取得」をベースに、区間総和取得の実装を考えてみる。
これも一筋縄では行かない。以下のようにmaxを加算に置き換えるだけでは、正しく動作しない。
static S op(S l, S r) { return l + r; }
0,1,2,3を2に置き換えたのだから、全体の総和は6になって欲しい。
apply[0...3) <= 2 calc [0...5) => 4
セグメント木は、区間内の全ての要素を更新する必要が無いように、大きな区間で値を保持する。applyした直後は、以下のようになる。 （以下の図はSとFを混同しているので正確で無い）
[ ? ] [ ? ] [ ? ] [2] [?] [e] [e] - - 2 e e e e e
無対策で、[0..3]の総和を取ろうとすると、
[ ? ] [ 4 ] [ ? ] [2] [2] [e] [e] - - 2 e e e e e
で、4になってしまう。
解決するには、[0..1]の区間の長さをopに伝える必要がある。
どうするのか？これの答えは、AtCoderLibraryのサンプル実装に掲載されていて、以下が必要になる。
- 区間の長さを S に保持する
- セグメント木全体を初期化する。
S を以下のように定義。保持するのは総和と区間の長さ。
struct S { int sum; int size; };
opは、sum の値を使って加算する。区間長も加算されるはずなので、こちらも加算する。
static S op(S l, S r) { return S{l.sum + r.sum, l.size + r.size}; }
opに基づいて e を定義する。都合が良いのは、S{0,0}。
size が 0 になるような要素はあり得ない（範囲外の要素としてはあり得る）点に注意。
static S e() { return S{0, 0}; }
applyの中身であるmappingの実装。ここでsizeを使うことになる。 区間を一様に塗り替えるのだから、sumは「値☓区間長」。
static S mapping(F f, S x) { return f.ignore ? x : S{f.setter*x.size, x.size}; }
lsegtraitは以上で十分。
ところで、size が 0 になるような要素はあり得ないため、初期値をeにすることは出来ない。 コンストラクタでセグメント木全体を初期化しなければならない。
初期値は、総和0・長さ1とした。
int main() { int N; cin >> N; vector<lsegtrait::S> inits(N); fill(inits.begin(), inits.end(), lsegtrait::S{0, 1}); lazy_segtree<LSEGTRAIT(lsegtrait)> segment(inits);
以上により、全体が動作できるようになったはず。以下にまとめを掲載する。
#define LSEGTRAIT(t) t::S, t::op, t::e, t::F, t::mapping, t::composition, t::id struct lsegtrait{ struct S { int sum; int size; }; struct F { int setter; bool ignore = false; }; static S op(S l, S r) { return S{l.sum + r.sum, l.size + r.size}; } static S e() { return S{0, 0}; } static S mapping(F f, S x) { return f.ignore ? x : S{f.setter*x.size, x.size}; } static F composition(F f, F g) { return g.ignore ? f : g; } static F id() { return F{0, true}; } lsegtrait() = delete; }; int main() { int N; cin >> N; vector<lsegtrait::S> inits(N); // 初期値のセットを忘れずに fill(inits.begin(), inits.end(), lsegtrait::S{0, 1}); lazy_segtree<LSEGTRAIT(lsegtrait)> segment(inits); while (true) { string cmd; cin >> cmd; if (cmd == "apply") { int begi, en, valu; cin >> begi >> en >> valu; segment.apply(begi, en, lsegtrait::F{valu}); cout << "apply[" << begi << "..." << en << ") <= " << valu << endl; } else if (cmd == "calc") { int begi, en; cin >> begi >> en; auto res = segment.prod(begi, en).sum; cout << "calc [" << begi << "..." << en << ") => " << res << endl; } else break; } cout << "complete!" << endl; return 0; }
heavy
区間線形加算・区間総和取得
対応する区間の情報を S と F に保持させると、出来ることが増える。以下は、その一例。
int sigmasum(int begin, int end) { // calculate begin + ... + end-1 return (end*(end-1) - begin*(begin-1))/2; } struct lsegtrait{ struct S { int sum; int begin; int end; }; struct F { int begin; int end; }; static S op(S l, S r) { return S{l.sum + r.sum, min(l.begin, r.begin), max(l.end, r.end)}; } static S e() { return S{0, numeric_limits<int>::max(), numeric_limits<int>::min()}; } static S mapping(F f, S x) { auto b = max(f.begin, x.begin); auto e = min(f.end, x.end); if (b >= e) return x; // 範囲外なら何もしない auto i = max(0, x.begin-f.begin); // 加算区間の開始番号を計算 return S{ x.sum + sigmasum(i, i + (e - b)), x.begin, x.end}; } static F composition(F f, F g) { return F{min(f.begin, g.begin), max(f.end, g.end)}; } static F id() { return F{numeric_limits<int>::max(), numeric_limits<int>::min()}; } lsegtrait() = delete; };
行列をもたせる例
行列とか載せたりすると楽しくなるよ
この問題は遅延でないセグメント木ですが…
おまけ・抽象化しなくて良いこともあるよ
https://github.com/buyoh/codeLib2/ に、以下のクエリを全て O(log(配列長)) で処理出来る遅延セグメント木を置いています。
codeLib2/segmenttree.hpp at master · buyoh/codeLib2 · GitHub
数え上げであれば割と太刀打ち出来ますが、ATLでは殆ど通用しなくなるため、レーティングが欲しいのであれば、抽象化セグメント木の勉強は必須です。
