前言
(trie) 树一般用于处理前缀字符串的匹配问题，但是其实在字符串问题上的作用并不大，一般都是拿来转化的。
(01trie) 可以用来维护异或最大值，同时也多出现在位运算的场合，尤其是按位贪心等技巧，需要在 (01trie) 上二分等，需要掌握。
众所周知，绝大多数复杂度不基于均摊的数据结构都是可以可持久化的，这里我们就来总结一下一些题目。
正文
trie
字符串问题
BSOJ4445【FJMTC2015#4】神牛的养成计划
这题可以用两个 (trie) 直接把问题转化成：询问((u,v))：有多少个编号满足在第一棵树(u)的子树内，在第二棵树(v)的子树内。
两维限制，很明显是一个二维数点，可持久化线段树维护即可。
BSOJ3889【省选模拟1】Kpm的MC密码
建完 (trie)树 后其实就是询问其一个子树内的权值第 (k) 大数，可以在树上跑一遍 (dfn)序 然后直接主席树。
01trie
异或最大值
BSOJ1340【BZOJ4260】异或REBXOR
容易发现可以找出这样一个“分界点”，使得前半部分和后半部分是两个取出来的区间。
于是我们考虑维护一下前缀异或最大值和后缀异或最大值，然后扫一遍，也就是枚举一遍分界点看哪里最优即可。
按位贪心
BSOJ6325【10.17题目】异或doubt
建出两棵trie树，然后开始dfs，尽量让当前位相同的匹配即可。
具体见这里。
可持久化trie
维护匹配前缀
P6088 [JSOI2015]字符串树
发现其实可以维护树上前缀(trie)，然后查询就是树上差分的询问，最后求得答案就是子树标记个数了。
可持久化一下就不用每次重建了，这也是树上前缀结构的常用技巧。
可持久化01trie
BSOJ3875【HDU4757】Tree
发现还是很显然的询问路径的异或最大和，可以树剖+(01trie)，但是我们也可以采用树上前缀数据结构和树上差分的技巧，维护前缀 (01trie)，然后答案就是一边差分一边二分地按位贪心即可。
P4735 最大异或和
比较模板的模板题，题目可以很容易转化成：询问一个区间内的数，取出一个与 (x) 异或的最大值。
那么直接对于每一个下标建立前缀(01trie)，可持久化一下即可，然后差分+(trie) 树上询问即可。
BSOJ2061【BZOJ3689】异或之
据传这类询问“第(k)大”值的题目的祖先是P2048 [NOI2010] 超级钢琴，因为大家写题解好像都提到先做这个..（然而我直到写下这些字的时候都还没做。
具体(trick)就是弄一个堆，然后以每一个位置作为“贡献点”，更新每一个位置的权值，然后加入堆，一个一个弹出直到弹出到第 (k) 个，那么就是我们要求的。
这道题就是假设每一个点作为 (j) ，然后维护可能的所有的 (i) 的异或最大值，同时动态更新次大值，第三大值...使用可持久化(01trie)即可完成这个任务。
注意这道题的坑点，就是我们可以每次修改后把构成最大值的那个选出来的数在(01trie)中删掉贡献，但是要注意删掉的话我们也需要新开节点，因为这里的可持久化是共用节点的！！1
P4098 [HEOI2013]ALO
直接统计似乎并不好做，因为要找到区间的次小值，那么其实我们可以换一种思路来做，假设当前点就是区间的次小值，然后求出满足这个条件的左右边界，然后分别询问两段区间和这个数异或得到的最大值即可。
也就是可以使用可持久化(01trie)来维护就行了。
至于怎么维护这个区间，两种办法，一是从小到大更新值，然后每次二分即可，第二种也是枚举值，然后链表来维护前驱后继。
P5795 [THUSC2015]异或运算
首先我们发现 (n,m) 不同阶，肯定有问题，于是我们可以考虑一下枚举 (A_{i,j}) 中的 (i) 。
算一下复杂度，似乎 (O(nplogm)) 比较合适，于是考虑怎么做查询第 (k) 大的异或值。
我们发现，其实对于一个数和一个区间去匹配异或值然后求第 (k) 大的问题，是我们已经会的，就是直接在 (01trie) 上根据 (siz) 和当前位的 (0/1) 情况来二分最终答案即可。
那么现在无非是一个区间和一个区间，并且我们第一个区间可以一个数一个数地枚举，其实我们就可以看做是第一个问题了，但是主要区别就是二分判断的时候，我们直接让每一个数作为根同时往下一位跳，询问所有数当前位可以为 (0/1) 的个数之和，然后再正常判断即可。
感觉其实就很像(O(nlogn imes k))的“多树二分”的做法了（其实就是？）。
BSOJ1729【BZOJ2741】L序列
分块+可持久化(01trie)。
具体见题解，这里不赘述。
总结
现在遇到的一些技巧如下：
(1.)树上前缀可持久化(01trie)
(2.)直接枚举区间的条件（比如次小值），然后转化成单点对应区间后可持久化询问即可。
(3.)“第(k)大值”在(k)很小的时候，我们可以考虑直接用一个堆来维护，一个一个弹出即可。
(4.)在(01trie)树上二分的技巧，以及多树上二分的技巧。
(5.)(trie)树维护前缀后缀的子串匹配关系。