蟻本には再帰で書かれた Segment Tree が載っているが,うまく書けば再帰を使わず書くこともできる. 再帰あり gist9219b197f2a177931e54627003b51c6f 再帰なし gistfe04fcefcc5581d60da6150a621d549e それぞれの方法で長さ 200000 でランダムな 1000000 クエリに対して RMQ を書き,実行時間を比較した. (GNU C++ 5.1.0 で -O2 最適化オプションを付けた) それぞれの 1 クエリあたりの時間は以下のようになった. 実行時間 (ns) 再帰あり 179 再帰なし 74 再帰なしだとかなり速く,定数倍の重さは Fenwick Tree の高々倍程度のようだ. 問題: K: SOULBLOCK - 京都大学プログラミングコンテスト2015 | AtCoder 続きを読む 特に考察は必要なく