セグメント木 セグメント木は、区間更新・区間上の最小値や和などをO(logn)で求めることができるデータ構造です。 セグメント木を理解するために役立つリソース かつっぱさんの動画です。説明が丁寧なのでわかりやすいです。 part1では、セグメント木の雰囲…

AOJの問題 区間和の取得は普通にできるが、更新は工夫が必要。 二分木は区間和を保持する。 また、遅延配列はINFで初期化しておこう。これはフラグとして利用する。(更新後の値として与えられる可能性があるため、0はフラグの値として使えない。) 更新すべき…

AOJの問題 RSQ&RAQのコードを少し変更しただけ。 区間更新の場合は加算と違って、普通に値を代入するだけでよい。 遅延配列の要素は、更新クエリで与えられることのない値で初期化すること。これがフラグの代わりになる。 実装 #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

問題 nodeの値を保存しているだけではどの値がいつ更新されたモノなのかがわからないので、更新された時間も保持しておくことにする。 値を取得するときは、子から見ていって最新の更新時刻を持つnodeの値が現在の値になる。 管理する情報が増えただけで後は…