在luogu上找到一个高级数据结构的题单就开始慢慢刷。主席树（可持久化trie）这种东西我除了写过板子什么都不会，甚至板子都写不出来。
首先我引用一下题单发布者对这一部分的说明：
二、主席树&可持久化 Trie
主席树是在省选难度比赛中应用最为广泛的数据结构之一，而部分功能也可以用可持久化 Trie 代替，好写一些。
然而实际应用中解决普通值域问题多用主席树，而处理异或问题会用可持久化 Trie（事实上权值线段树也可以解决异或问题，但是复杂度稍大，也有题目涉及）。
我以前学习主席树的时候是根本不知道线段树合并怎么写的，这次学完线段树合并后再看主席树，感觉写法很相似，有很多共同之处。
P3834 【模板】可持久化线段树 1（主席树/可持久化 01Trie 模板题）
模板题，就学习一下主席树的写法，也没必要太过于纠结，写完后面的题就可以熟练掌握了。
P4735 最大异或和（可持久化 01Trie 解决异或问题模板题）
int query(int l, int r, int val, int h = 30, int res = 0) {
if (h < 0) return res;
int o = (1 << h) & val;
if (sum[r] - sum[l] == 0) return res;
if (!o && sum[rs[r]] - sum[rs[l]]) return query(rs[l], rs[r], val, h - 1, res| (1 << h));
else if (o && sum[ls[r]] - sum[ls[l]]) return query(ls[l], ls[r], val, h - 1, res | (1 << h));
else if (sum[rs[r]] - sum[rs[l]]) return query(rs[l], rs[r], val, h - 1, res);
else return query(ls[l], ls[r], val, h - 1, res);
}
我是这么写的，后来发现trie可能用ch[x][0],ch[x][1]会更好写一些。
P2617 Dynamic Rankings（权值线段树的简单扩展——树状数组套权值线段树维护待修改二维数点）
看着很恐怖的树套树。
主席树实际上是对出现次数这一信息做了前缀和。那么如果带修改操作，可以考虑用树状数组来维护这个前缀和就好了。
比较简洁的写法可能是对树状数组位置的获取、求和、变成左儿子、变成右儿子的操作封装。
P2633 Count on a tree（树上主席树套路）
利用树上差分的思想。两点间路径的出现次数=根到两点的出现次数-根到lca的出现次数-根到lca的父亲的出现次数。
注意建树顺序。
P2839 [国家集训队] middle（二分+主席树好题，启发了主席树在值域上建区间的套路）
据说找中位数就要二分答案。将>=mid的数变成1，<mid的数变成-1。如果一个区间的和非负，那么l = mid。否则r = mid - 1。
考虑整个数组，当mid变化成mid+1的时候，只有一个位置会发生变化，那这就可以用主席树来维护了！用主席树维护区间的前缀后缀最大子段和！
P5284 [十二省联考2019] 字符串问题（SA/SAM+线段树优化建图，需要可持久化）
不会做，代码基本是抄的。代码实现很有技巧（相对于我来说）。不可描述。
P4094 [HEOI2016/TJOI2016] 字符串（二分+主席树好题，主席树求两区间交的套路）
二分答案，找到第二个字符串s(c, c + mid - 1）,对应的后缀自动机的节点，然后用线段树合并维护一下每个节点的endpos集合，查一查就好。
P6071 [MdOI2020] Treequery（我 吹 我 自 己，主席树与虚树理论结合，也有不太优美的倍增+主席树做法）
又一道劝退题，区间lca等价于dfs序最小最大的两个节点的的lca。考虑换根后的dfs序，一种可行的方案是dfn[x] -> dfn[n] -> dfn[1] -> dfn[x-1]。
P3899 [湖南集训] 更为厉害（启发了主席树能解决的一大类问题——二维数点）
b要么是a的祖先，要么是和a距离不超过k的后辈。显然是祖先的情况就是深度。
然后问题就变成了查字树中深度在一个区间中的点的size - 1 求和。前缀和dfs序以深度为权值就好。
P4197 Peaks（主席树与 Kruskal 重构树的直接结合，也有并查集的做法）
离线，按x排序，然后合并，然后询问。
P4175 [CTSC2008] 网络管理（毒瘤的树上线段树套线段树，可以思考套的顺序对应套路）
树上树套树！树上第k大可以利用树上差分解决，修改可以用树状数组解决。注意实现的方法，感觉不好的实现很劝退。
P3293 [SCOI2016] 美味（主席树处理平移后的异或问题）
在询问的过程中的区间会有x的偏移。
P5283 [十二省联考2019] 异或粽子（可持久化 Trie 入门题，可以思考 k 较大的情况）
利用堆来做。考虑将以每个点为右端点的最大的粽子放进去，然后在堆里面取，取出某个点的第k大时，放入这个点的第k+1大。
P5795 [THUSC2015] 异或运算（与前一题异曲同工，在一堆可持久化 Trie 上同时做二分）
看着和前面一题很想，改一改tle了。
如题，在多个可持久化trie上一起二分，注意实现。
补充题：UOJ 266 [清华集训2016] Alice和Bob又在玩游戏（Trie 的全局异或标记，Trie 树合并，非常重要的技巧）
主要是个博弈题，Trie树合并查询什么的相比前面的应该都是小问题。