1 线性基

不会。

2 字典树

用 Trie 解决 xor 的核心思想就是：贪心地选相反的一位。下面通过题目说明。

2-1 超水例题

题意

给你 \(n\) 个数 \(a_i\)，\(T\) 次询问，每次询问一个数 \(x\)，求选取一个 \(a_i\) 使 \(a_i \text{\ xor\ }x\) 最大是多少。

\(n,T\le 10^5,a_i\le 2^{30}\)。

题解

首先是插入。

我们把 \(a_i\)​​ 拆分成二进制，从高位到低位插入进 01字典树 中。比如一个数二进制为 1010，则：

X---1---2---3---4
  1   0   1   0

差不多这个意思……

在每个叶子节点我们设 \(w_i\)​，为根到此叶子代表的数字是什么。显然插入到结尾的时候顺便放入赋值就行了。

再下是查询。

对于 \(x\)​ 拆分成的二进制，从高到低把它放在字典树中，到了第 \(d\) 层的某一点，如果 \(x\) 二进制从高到低的位是 1，则走此点的 0 儿子；如果位是 0，则走此点的 1 儿子。（当然，如果此点只有一个儿子，就只能走这个儿子了）

最后走到叶子节点，则答案就是 \(x\ \text{xor}\ w_i\) 啦。

2-2 最大异或和

链接，题意略。

建立可持久化字典树，云云。

2-3 异或粽子

略。