Segment Tree

作成日:2019.04.05
最終更新日:2019.04.05

目次

  1. 概要
  2. 計算量
  3. 実装

できること

 モノイドの配列に対して、区間に同一の演算を行ったり累積演算を取得したりするのが$O(T\log N)$でできるデータ構造である。 但し、演算にかかる計算量を$O(T)$とした。
注:当ページは「遅延セグメントツリー」の話である。また「セグ木」と略す。

目次に戻る

所感

 多くの演算は適切な単位元を入れるとモノイドをなす上、区間に対する操作もよく行われるので頻出のデータ構造である。 セグ木にどんな構造を乗せるかがメインとなる問題もあるが、ほとんどは考察の末に区間演算が高速にできれば良いからセグ木を使うというパターンである。
 また「セグ木で殴る」と言われるように、これを使うとそれほど頭を使わずに解けることもある。 しかしその汎用性から、区間に対する操作があったらセグ木で解くことしか考えられなくなる「セグ木依存症」に陥る人も多い(要出典)。 累積和、差分をとるなどといった他の典型も忘れないようにしたい。
 ちなみに、私の「セグ木万能説」を打ち砕いたのはCodeforces Round #371 D : Animals and Puzzleである。

目次に戻る

出題実例、応用例

3つ目はセグ木メインの問題。4つ目はセグ木の練習問題。

AGC019C : Fountain Walk本サイトでの解説
ARC085F : NRE本サイトでの解説
ARC008D : タコヤキオイシクナール
AOJ DSL_2_*

目次に戻る

広告

自己紹介

赤になりたい競技プログラマー/バランス重視
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

広告