Segment Tree

• 以下のような性質を持つデータ構造

• 性質というか操作ができる配列

• 配列に対して以下の操作ができる

  • 長さnで初期化する
  • i番目の要素の値をxにする
  • l番目からr番目までの和を求める

• 初期化は$\Theta (n)$時間、他は$O(\log (n))$時間

  • 実装によっては区間和は$O(\log (r-l))$時間だったりするらしい

• references

  • https://zenn.dev/magurofly/articles/3aa1084dfecce2
    • 初学者向け
  • https://rsk0315.hatenablog.com/entry/2020/07/05/184929
    • えびちゃん
    • スライドへのリンクとかもあってそのスライドは結構初学者向けっぽい