再帰関数書きたくない！！！(セグメント木編)

はじめに

再帰関数はとっても便利なもので、これを使うとアルゴリズムがシンプルに実装できることがありますね。競技プログラミングでもよく使われますが、 pythonだとどうしてもこういうのを書かざるを得ません。

import sys
sys.setrecursionlimit(200000)

これ、美しさを損ねている感じがしますし、なるべくなら書きたくないですよね。それに、たかだかスタック領域のサイズ分しか入力を扱えないというスケーラビリティの問題もあります。なので、書かないでなんとかしましょう。

今回は、セグメント木を再帰無しで書いてみます。

配列のある範囲内の最大・最小等をうまく求めることができるようになるデータ構造です。偉大な先人がていねいにまとめてくださっているので、詳細はそこを見るとしましょう。例えば以下です。

今回は1つのソースコードに両方まぜています。 queryが再帰なし版、query_recと__query_recが再帰版になります。

セグメント木の場合は、再帰にすると引数が多くて紛らわしいですね。。。ボトムアップに再帰なしでやるとシンプルな感があります。ぐぐると再帰版が出てくることが多そうな印象がありますが、これに限っては再帰なくしたほうがわかりやすくないですかね？

このコードはある程度は動く・・・かな・・・と思う・・・