再帰を使わない Segment Tree
蟻本には再帰で書かれた Segment Tree が載っているが,うまく書けば再帰を使わず書くこともできる.
再帰あり
gist9219b197f2a177931e54627003b51c6f
再帰なし
gistfe04fcefcc5581d60da6150a621d549e
それぞれの方法で長さ 200000 でランダムな 1000000 クエリに対して RMQ を書き,実行時間を比較した.
(GNU C++ 5.1.0 で -O2 最適化オプションを付けた)
それぞれの 1 クエリあたりの時間は以下のようになった.
実行時間 (ns) | |
---|---|
再帰あり | 179 |
再帰なし | 74 |
再帰なしだとかなり速く,定数倍の重さは Fenwick Tree の高々倍程度のようだ.