可持久化字典树
算法简介
一种可以维护历史版本的字典树，实现方面与可持久化线段树类似，主要用于维护区间异或和。
时间复杂度和空间复杂度均为 $O\left(m\log n\right)$。
算法例题
题意
给定序列 $a_1,a_2\cdots a_n$，支持下述操作：
- 在序列末尾添加一个数 $x$
- 给定 $l,r,x$，询问 $\max_{l \le p\le r} x\oplus(a_p\oplus a_{p+1}\oplus \cdots \oplus a_N)$，其中 $N$ 表示当前序列长度
题解
设 $S_i=a_1\oplus a_2\oplus \cdots \oplus a_i$，于是询问操作变为 $\max_{l-1\le p\le r-1} x\oplus S_N\oplus S_p$。
考虑对序列 ${S_0,S_1,S_2\cdots S_n}$ 建立可持久化字典树，修改操作等价于在最后版本基础上插入新元素。
查询操作用类似主席树的方法查询区间中每个数与 $x\oplus S_N$ 异或的最大值即可。
算法练习
习题一
题意
给定 $n$ 个互异的数。求 $a_i\oplus a_j$ 的最大值，其中 $i,j\in [l,r]$ 且 $a_i$ 为 $a_l,a_{l+1}\cdots a_r$ 的次大值。
题解
枚举每个次大值，显然次大值确定时区间尽可能向两边拓展可以取到最优解。
考虑对 $a_i$ 进行排序，然后通过双向链表确定最优区间(至多存在两个)。区间查询通过可持久化字典即可完成。
时空间复杂度 $O(n\log v)$。
习题二
题意
给定 $n$ 个互异的数，求前 $k$ 大的区间异或和。
题解
前缀异或和处理，问题转化为求前 $k$ 大的点对异或和。
考虑用优先队列维护每个固定点 $i$ 对配对区间 $[0,i-1]$ 的最佳答案，设 $i$ 的最大答案位置为 $k_i$。则全局最大答案一定为某个 $(k_i,i)$。
弹出全局最大答案，固定点 $i$ 的第二大答案位置一定在区间 $[0,k_i-1]$ 和 $[k_i+1,i-1]$，将其加入优先队列。
重复 $k$ 次即可得到全局前 $k$ 大答案。
习题三
题意
给定一个长度为 $n$ 的序列 $X$ 和长度为 $m$ 的序列 $Y$，定义矩阵元素 $A_{i,j}=X_i\oplus Y_j$，接下来 $q$ 个询问。
每次询问 $\max_{l_1\le i\le r_1,l_2\le j\le r_2}A_{i,j}$。
