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

hamayanhamayan's blog

競技プログラミングにおけるセグメントツリー問題まとめ

セグメントツリー

  • 数列の区間に対してのクエリに答えるデータ構造
  • 問題集 Codeforcesのやつ 基本 基本 発展的 激ムズ
  • 覚えるべきなのは「普通のセグメントツリー」「遅延評価セグメントツリー」「動的セグメントツリー」(「シフトセグメントツリー」「2Dセグメントツリー」)
  • シフトセグメントツリー : 一般的なセグメントツリーに全ての要素をシフトさせる機能を付けたもの、ただ基準点を決めてずらしていくだけの実装

問題

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

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

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

動的セグメントツリー

シフトセグメントツリー

2Dセグメントツリー

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