永続データ構造
- persistent data structures
- 解説
- 色々ある「永続配列」「永続セグメントツリー」「永続Union-Find」「永続木」「永続平衡二分木」「永続WaveletMatrix」参考
- 部分永続。最新版のみ変更可能、Undoができる機構がある。履歴は一直線。
- 完全永続。昔のどのバージョンからでも変更でき、履歴が全て残っている。履歴は木。
- 永続配列があれば永続Union-Findが作れるらしい
- 永続配列は永続木があれば作れるらしい
- 部分永続Union-Findの資料
- 部分永続はスタックで履歴を残しておいて逆操作をしていって戻すやり方がある（要出典）多分そのやり方でやってる
- 平衡二分木を永続化するときは赤黒木が最良らしい
問題
- 完全永続セグメントツリー
- SPOJ D-query
- CF429 Destiny (要素add,特殊クエリ)
- 部分永続セグメントツリー
- CSAcademy Tree Nodes Sets (要素update,全体の総和)
- 部分永続UnionFind
- CF446 Envy
- AGC002 D. Stamp Rally 解説1 解説2
- AC Union Sets（ご指摘いただきました！）
- 完全永続Trie
- CodeChef Gotham PD
- CF457 Jamie and To-do List （+完全永続配列, 完全永続平衡二分木でも解けるらしい）
- その他(分からんやつとか)
- CF368 Persistent Bookcase 完全永続配列(反転操作がある 実装例)
- CF276 Sign on Fence (部分？完全？)永続セグメントツリー 解説
- CF265 The Classic Problem 完全永続遅延評価セグメントツリー
未確定
- HR Travel in HackerLand 解説
- HR Sequential Prefix Function
- http://pekempey.hatenablog.com/archive/category/Persistent%20Segment%20Tree
- https://i.cs.hku.hk/~provinci/training2016/notes4.pdf
- https://blog.anudeep2011.com/persistent-segment-trees-explained-with-spoj-problems/
- http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2012%2FPractice%2F春コンテスト%2F講評&openfile=I.pdf
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2563
