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

AOJの問題 RMQ and RUQ、RSQ and RAQからそれぞれ関数をとってきて貼り付けただけでは解けない。 加算の際に多少工夫が必要。 RMQ and RUQでは、2分木に区間和を保持していたが、今回必要なのは区間の最小値なので、それを保持する。 加算の際には、区間の全…

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

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

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

問題 RSQのコードを少し弄れば解ける。 具体的には、一点更新→一点取得、区間取得→区間更新、のように取得と更新の役割を逆転させる。 かつっぱさんの動画がわかりやすい。 実装 #include <bits/stdc++.h> using namespace std; struct RAQ_SegTree { int n; // 葉の数 vect</bits/stdc++.h>…

問題 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>…

問題 RMQは、与えられた区間の最小値を求めるというもの。 セグメント木を使って解きます。 実装 セグメント木の実装の中で何をしているかはコメントに書いてあります。 AOJのテストケースはパスしましたが、バグが潜んでいるかもしれません。 #include <bits/stdc++.h> usi</bits/stdc++.h>…