可持久化：支持查询历史版本和在历史版本上修改
可持久化数组
主席树做即可。
【模板】可持久化数组（可持久化线段树/平衡树）
可持久化并查集
可持久化并查集
要按秩合并。（路径压缩每次建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: 无聊的游戏