Segment Tree
作成日：2019.04.05
最終更新日：2019.04.05
目次
できること
モノイドの配列に対して、区間に同一の演算を行ったり累積演算を取得したりするのが$O(T\log N)$でできるデータ構造である。
但し、演算にかかる計算量を$O(T)$とした。
注：当ページは「遅延セグメントツリー」の話である。また「セグ木」と略す。
所感
多くの演算は適切な単位元を入れるとモノイドをなす上、区間に対する操作もよく行われるので頻出のデータ構造である。
セグ木にどんな構造を乗せるかがメインとなる問題もあるが、ほとんどは考察の末に区間演算が高速にできれば良いからセグ木を使うというパターンである。
また「セグ木で殴る」と言われるように、これを使うとそれほど頭を使わずに解けることもある。
しかしその汎用性から、区間に対する操作があったらセグ木で解くことしか考えられなくなる「セグ木依存症」に陥る人も多い（要出典）。
累積和、差分をとるなどといった他の典型も忘れないようにしたい。
ちなみに、私の「セグ木万能説」を打ち砕いたのはCodeforces Round #371 D : Animals and Puzzleである。
出題実例、応用例
| AGC019C : Fountain Walk | 本サイトでの解説 |
| ARC085F : NRE | 本サイトでの解説 |
| ARC008D : タコヤキオイシクナール | |
| AOJ DSL_2_* |