はまやんはまやんはまやん

hamayanhamayan's blog

競技プログラミングにおけるセグメントツリー問題まとめ [セグメントツリー, BIT, 遅延評価セグメントツリー]

セグメントツリー

  • 数列の区間に対してのクエリに答えるデータ構造
  • 問題集 Codeforcesのやつ 基本 基本 発展的 激ムズ
  • 覚えるべきなのは「普通のセグメントツリー」「遅延評価セグメントツリー」「動的セグメントツリー」「2Dセグメントツリー」
    • 遅延評価セグメントツリーの資料 資料1
  • セグメントツリーもDP同様に難しいやつから簡単なやつまで幅があるので少しずつやっていこう(といいつつ以下は難しい問題ばかりだが)
  • 2DBITの何か

応用問題

遅延評価セグメントツリー([l,r)をvにする +α)

遅延評価セグメントツリー([l,r)にvを足す +α)

遅延評価セグメントツリー(その他)

特殊なマージをするセグメント木

動的セグメントツリー

シフトセグメントツリー

2Dセグメントツリー

3Dセグメントツリー

2DBIT

セグメントツリーにBITなどを載せるテク

更新や取得を枝刈りしたり、更新回数が限られている関係で間に合う(奈良木?)