#SegmentTree
セグメント木を育てる 2
・問題を区間に言い換えるARC033-C_データ構造
集合Sに数字が追加されていくので、下からX番目の数字が何かを答える問題です。
set等で解けそうな感じですが、一番大きいor一番小さいはO(1)で分かるのですが、下からX番目は辿っていくしかなくO(N)かかっちゃいます。
・数字Xが下から何番目かを記録する配列を持つ。
EX.5 8 3 9 2と数字が追加されるとします。
0 0 0 0
セグメント木を育てる 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)となるので、