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

hamayanhamayan's blog

競技プログラミングにおける永続データ構造問題まとめ

永続データ構造

  • persistent data structures
  • 解説
  • 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考
  • 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。
  • 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。
  • 永続配列があれば永続Union-Findが作れるらしい
  • 永続配列は永続木があれば作れるらしい
  • 部分永続Union-Findの資料
  • 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある(要出典)多分そのやり方でやってる
  • 平衡二分木を永続化するときは赤黒木が最良らしい

問題