#AOJ
セグメント木を育てる 3
・例題AOJ_Range Update Query (RUQ)
RMQとの違いは、更新が一点更新ではなく、区間更新となっている点です。
区間なのでセグ木で解けそうですが、区間を更新する際に一つずつ更新するしかなく、O(QN(logN))の計算量がかかります。
N=Q=10^5が最大なので、TLEになります。
・遅延評価セグメント木上記のような区間更新をO(logN)でできるデータ構造が遅延評価セ
セグメント木を育てる 1
ぬるからです。
青になるために、セグメント木(SegmentTree)なるものの習得が必須だと感じました。
少し勉強したり、ライブラリとして作ったので纏めてみます。
・例題AOJ:Range Minimum Query (RMQ)
セグメント木のお手本のような問題です。
単純に考えれば、updateにO(1)、findにO(N)かかります。
クオリが全てfindだった場合、O(QN)となるので、