可持久化Trie

简介

Trie树相当重要的一个用途就是用于处理最大异或和的问题。

Trie树有和线段树相当的结构，也可以将每次修改节点，转化为新建节点，从而实现可持久化和访问历史版本。

当想知道一个区间的Trie树时，可以用两个前缀的Trie树相减。

void ins(int x) {
    
}

bzoj 3261
维护一个数字，支持在末尾添加一个数字，区间中选一个子区间，和 $x$ 异或最大

spoj MAXOR
可持久化Trie，分块。

bzoj 4103
输入序列 $\{a_1, a_2, \ldots, a_n\}, \{b_1, b_2, \ldots, b_m\}$ 两两异或
生成 $n \times m$ 的矩阵，每次询问一个矩形区域，问区域内第 $k$ 大的数。