読者です 読者をやめる 読者になる 読者になる

(o_o)

ブログ。

再帰を使わない Segment Tree

蟻本には再帰で書かれた Segment Tree が載っているが,うまく書けば再帰を使わず書くこともできる.

再帰あり

gist9219b197f2a177931e54627003b51c6f

再帰なし

gistfe04fcefcc5581d60da6150a621d549e


それぞれの方法で長さ 200000 でランダムな 1000000 クエリに対して RMQ を書き,実行時間を比較した.
(GNU C++ 5.1.0 で -O2 最適化オプションを付けた)
それぞれの 1 クエリあたりの時間は以下のようになった.

実行時間 (ns)
再帰あり 179
再帰なし 74

再帰なしだとかなり速く,定数倍の重さは Fenwick Tree の高々倍程度のようだ.