可持久化：支援查詢曆史版本和在曆史版本上修改
可持久化數組
主席樹做即可。
【模闆】可持久化數組（可持久化線段樹/平衡樹）
可持久化并查集
可持久化并查集
要按秩合并。（路徑壓縮每次建logn條鍊，會卡爆空間MLE）
主席樹節點，維護father（是一個真實下标），維護dep（集合的最大深度），
一個關鍵函數是query，找到代表實際位置為pos的節點的編号
對于一個版本，
合并：先找到這個兩個位置的集合的根節點。
不在同一個集合裡的話，就合并。
合并的時候，建立一條鍊，并且更新father，dep還是原來節點的dep
如果和連向的father的dep相同的話，那就把father的點的dep++，象征這個新連上的集合深度是最深深度。
（++deep的時候，可以不建立新節點。因為隻是影響一些按秩合并效率，但是基本沒有影響）
（upda：2019.3.5 不會影響的。因為是對新節點的deep++，和之前版本沒有任何關系）
查詢：直接查詢即可。
【模闆】可持久化并查集
不能在曆史版本上更改的可持久化并查集。（也就是，曆史版本形成的樹是一條鍊）
（可持久化并茶幾O(logn)： （NOI2018D1T1） 每個點記錄每時每刻在哪個集合裡 用vector記錄pair 合并的時候，啟發式合并，然後暴力修改 最多O(n)個集合，每個集合記錄點權最大值 查詢的時候 二分找到這個時間段 查詢集合點權最大值即可 ）
可以做到：空間O(nlogn)時間O(nlogn)
%%ImmortalCO
可持久化平衡樹：
1.還是主席樹做即可。
權值暴力開到-1e9~1e9（我腦殘了一下，還加了偏移量。。。）因為動态開點。。空間限制1GB
然後做就好了。
注意前驅後繼的寫法；
可持久化平衡樹
2.fhq-Treap？
留坑
[學習筆記]FHQ-Treap及其可持久化
例題：bzoj3946: 無聊的遊戲
可持久化0/1Trie
其實就類似于主席樹。（哪裡都是主席樹啊。。。）
維護一個序列字首的資訊。
每次加入一個點，在前一個的基礎上，加入的是一個log(val)的鍊。
額外維護一個sz，表示，前i個位置，走到這個位置，往下還有多少個數。（就類似于主席樹）
然後，給一個x，如果要找區間最大異或值，直接sz差分，判斷有無，然後貪心走即可。
例題：模闆：最大異或和
變一下形，就可以當“給一個x，找區間一個值異或，使得值最大”
最大異或和
[TJOI2018]異或
維護兩個可持久化Trie，一個dfn序，處理子樹。一個維護到樹根的資訊。
子樹，dfn序直接查詢
路徑，拆成x到lca，y到lca分别差分查詢。
注意數組大小，根節點還有2*N個空間。。。。。
31*N*2+2*N
異或
可持久化用途
可持久化目的主要就是充分利用不會動的資訊，減少時空的浪費
1.曆史值查詢：模闆，以及可持久化trie和主席樹的差分
2.路徑壓縮，任意字元集AC自動機
3.當做标記：bzoj3946: 無聊的遊戲