以下の内容はhttps://blog.hamayanhamayan.com/entry/2017/05/21/001252より取得しました。
永続データ構造
- persistent data structures
- 解説
- 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考
- 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。
- 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。
- 永続配列があれば永続Union-Findが作れるらしい
- 永続配列は永続木があれば作れるらしい
- 部分永続Union-Findの資料
- 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる
- 平衡二分木を永続化するときは赤黒木が最良らしい
問題
- 完全永続セグメントツリー
- 部分永続セグメントツリー
- 部分永続UnionFind
- 完全永続Trie
- その他(分からんやつとか)
以上の内容はhttps://blog.hamayanhamayan.com/entry/2017/05/21/001252より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14
