固定個数の値の列が与えられた時に、その区間に対して演算することが対数時間でできるデータ構造
-
AtCoderにおいて結構頻出する
-
プログラミングコンテストでのデータ構造 秋葉 拓哉 p.33~
-
値の更新 O(logN)
-
区間に対する演算 O(logN)
- 例えば加算なら「区間の和」、maxなら「区間のmax」となる
- 可能な演算については遅延伝搬セグメント木を参照
要素の削除はできないけど、総和なら削除の代わりに0で更新、最小値なら十分大きな数で更新すれば良いので実害ない。
最小値を効率的に求める方法としてheapqがあるが、こちらはランダムアクセスで更新が素直にできないので、削除を無効な値の読み飛ばしで実現するアプローチになる。
僕の実装 https://judge.yosupo.jp/submission/12659
- Static RMQなので一括で構築してる
- Point Add Range Sum
- →後でセグメント木のバージョンも作る