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

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

AOJの問題 区間加算と区間和の取得を同時にこなさないといけないので、普通のセグメント木だと難しくなってくる。 そこで、遅延評価セグメント木を導入する。 普通のセグメント木では、区間更新にO(nlogn)だけかかってしまうが(区間更新・一点取得の場合は別…

問題 RMQでは0-indexedだったのに、こっちは1-indexedになってて引っかかった。 RMQのコードを少し弄っただけです。 実装 何をやっているかはコメントに書いてあります。 #include <bits/stdc++.h> using namespace std; struct RSQ_SegTree { int n; // 葉の数 vector<long long> node</long></bits/stdc++.h>…