セグメント木
固定個数の値の列が与えられた時に、その区間に対して演算することが対数時間でできるデータ構造 AtCoderにおいて結構頻出する
値の更新 O(logN)
区間に対する演算 O(logN)
例えば加算なら「区間の和」、maxなら「区間のmax」となる
要素の削除はできないけど、総和なら削除の代わりに0で更新、最小値なら十分大きな数で更新すれば良いので実害ない。
最小値を効率的に求める方法としてheapqがあるが、こちらはランダムアクセスで更新が素直にできないので、削除を無効な値の読み飛ばしで実現するアプローチになる。 僕の実装
→後でセグメント木のバージョンも作る