01-trie 是一种特殊的 trie 树，是将整数作为二进制形式插入到 trie 中形成的字典树，其字符集为 $\{\mathtt0,\mathtt1\}$。01-trie 能够高效地维护许多关于异或的问题。
维护异或最大对
给定一个长度为 $n$ 的数组 $a_1,a_2,\dots,a_n$，你需要求出最大的异或对，即 $(i,j)$ 使得 $i\neq j$，$a_i\oplus a_j$ 最大。
贪心的想，如果我们知道了所有数的二进制表示，当想求最大的 $a_i\oplus x$ 时，我们只需要让 $x$ 的高位与 $a_i$ 对应的位尽量不同就可以了。（一个高位可以抵得上剩下的所有低位。）
因此我们枚举 $i$，并将 $a_1,a_2,\dots,a_{i-1}$ 全部从高位到低位地插入到 01-trie 中。接下来我们在 trie 中查找答案，从根节点向下跳，如果能走到与 $a_i$ 当前位不同的方向就一定走，否则只能走另一侧。最后走下来的路径异或上 $a_i$ 就是对于 $a_1,a_2,\dots,a_i$ 的最大异或对。
这样做的时间复杂度显然是 $O(n\log V)$。
维护异或和
给定一个可重集 $\{a_1,a_2,\dots,a_n\}$，要求支持以下四种操作：
- 求出集合中所有元素的异或和。
- 向集合中添加一个新元素 $v$。
- 从集合中删除 $v$。（有多个就只删一个）
- 将集合中所有元素增加 $1$。
首先我们考虑没有第四个操作怎么做。
我们发现求异或和只需要考虑 01-trie 每一层上 $1$ 的奇偶性，而不必考虑 trie 中具体放入了哪些数。因此 trie 每个节点维护以下三个信息：
ch[0/1]，左右儿子。w，该节点子树中存储的数的个数。xorsum，该节点子树中所有数的异或和。
我们发现本质上插入和删除是一样的：插入两次和删除都会使得这个数的贡献变成 $0$。
因此我们想一下怎么插入：
首先我们要决定以从高到低还是从低到高的顺序插入。为了方便第四种操作，这里采用从低到高的顺序。
其次要考虑在插入的过程中如何维护以上信息。为了方便由下到上地合并信息，使用递归的方式来插入。
一开始先建出 trie 结构，并在数结束的节点上让 w 值加 $1$，代表多了一个数。
返回的时候我们要合并左右儿子的信息。因为儿子的位数高度比父亲高一位，因此首先要将儿子的 xorsum 均左移一位再异或起来。再考虑多余的贡献，显然由 $1$ 方向的儿子提供，而具体有多少个 $1$ 要额外增加要看 w[ch[1]]，如果是奇数就有贡献，否则没有。
最后只需要将本节点的 w 设为儿子的 w 之和。
有没有注意到一个问题？
在刚才的过程中 w 的数值没有被关心，被关心的其实是 w 的奇偶性。
所以我们完全可以将上面所有的加法全部变成异或。也许这样能快点
代码：
1 | il void maintain(int u) { |
MAXH 的作用是限制每个数的长度，让每个数一样长。
删除很简单，只需要再插入一遍。查询很简单，只需要查询 $root$ 节点的 xorsum。关键在于全局加 $1$。
我们考虑一下在二进制时加 $1$ 是什么样的。
$\color{000000}10101101000\color{ff0000}11111\color{000000}+1=1010110100\color{0000ff}1\color{ff0000}00000$。
可以明显发现加 $1$ 就是把后缀 $1$ 全部变成 $0$，再在这个后缀的前面加一个 $1$。
因此在 trie 上这个过程很好实现：首先交换左右子树，因为如果当前位是 $0$，那么它就应该变成 $1$，因为它标志着后缀 $1$ 的结束；如果当前位是 $1$，那么它也应该变成 $0$。其次我们要进入先前的 $1$ 子树，也就是现在的 $0$ 子树继续修改。先前的 $0$ 子树已经不能继续修改了，因为后缀 $1$ 已经结束。
到这里就不难发现由低到高顺序建树的好处：我们把相同的后缀压在了一起，这样修改后缀时能一起修改。
代码：
1 | il void add_1(int u) { |
例子：P6018 Fusion tree
给定一棵树，每个点有点权。你需要支持三种操作：
- 将与一个点 $u$ 直接有边相邻的所有点权值都加 $1$。
- 将一个点 $u$ 的权值减 $v$。
- 查询与一个点 $u$ 直接有边相邻的所有点权值的异或和。
首先常见的 trick 是在处理树上相邻的信息时常常将儿子与父亲分开考虑。这里也可以这样做。
我们注意到这里有异或和、加 $1$，考虑使用 01-trie 维护。
对每个节点开存储所有儿子的 01-trie，那么三种操作分别是这样的：
- 首先对该节点的 trie 全局加，再暴力修改父亲的权值。注意要在改点权之前先在父亲的父亲的 trie 中将父亲的点权删除、再插入加一后的结果，最后再修改。
- 直接暴力修改即可。也要修改父亲的 trie。
- 直接查询即可，儿子异或上父亲。
然而这样是过不了的，原因是什么呢？原因在于我们暴力修改的时候拿到的值 $a_u$ 并不是真正的 $a_u$，因为父亲向儿子加 $1$ 的贡献只在父亲的 trie 中有体现，而并没有直接贡献到儿子上。
因此我们需要对每个点再维护一个 $tag$，表示这个点被全局加 $1$ 的次数，这样查询 $a_u$ 的时候应该再加上父亲的 $tag$ 再说真正的值。
总时间复杂度为 $O(n\log V)$。
01-trie 合并
很简单，类似 seg 合并。
1 | il int merge(int u,int v) { |
例子：P6623 树
给定一棵点有点权的有根树，$1$ 为根。定义一个点的价值 $val(u)$ 为
求出 $\sum\limits_{i=1}^nval(i)$ 的值。
小小简单题。考虑从下往上合并答案。
对于每个点开一棵 trie 存储子树内所有点的权值加深度。
对于点 $u$，我们先求出所有的儿子 $v$，并把其 trie 合并起来，然后再全局加 $1$，插入 $a_u$，再查询异或和累加起来。
时间复杂度 $O(n\log V)$。
例题们
2019十二省联考 异或粽子
对于一个长度为 $n$ 的数列 $a_1,a_2,a_3,\dots,a_n$，生成一个上三角矩阵
其中 $b_{lr}=\bigoplus\limits_{i=l}^ra_i$。你需要求出 $B$ 矩阵中前 $k$ 大的元素之和。
首先这个上三角很烦人，我们把它扩充成整个矩阵，即让 $k:=2k$，最后再把答案除以 $2$。
其次再做前缀异或和，这样就变成了给定 $s_0,s_1,\dots,s_n$，求两两异或前 $k$ 大之和问题。看到异或考虑使用 01-trie 维护。
01-trie 如何维护异或第 $k$ 大
先想想我们怎么维护异或最大值。就是从高向低位建 trie，尽量向与 $x$ 对应位不同的方向走，最后的数就是答案。
这给了我们一个思路，就是走一个分叉可以确定左右两边之数与 $x$ 异或的总体大小关系。假设 $0$ 儿子有一个数 $a$，$1$ 儿子有一个数 $b$。不妨设 $x$ 当前位为 $1$，那么向 $0$ 儿子走异或大小一定比向 $1$ 儿子走答案大，也就是说可以比较出 $a\oplus x>b\oplus x$。
我们记录 $u$ 点子树内数的个数。这样假设当前节点是 $u$，我们要求解异或 $x$ 第 $k$ 大，不妨设 $x$ 这一位是 $1$。那么我们可以求 $0$ 儿子内数的个数，假设是 $w$。我们比较 $k$ 和 $w$ 的大小关系：
- $k\le w$，那么第 $k$ 大一定在 $1$ 子树内，向 $1$ 侧递归下去；
- $k>w$，第 $k$ 大在 $0$ 子树内，向 $0$ 侧递归。
这个过程非常像线段树上二分。时间复杂度也是优秀的 $O(\log V)$。
有了这个方法我们再来看这个题，就有了这么一个思路：
- 首先对于每个 $s_i$，建出 01-trie。
- 对于每个 $s_i$，求它和别的 $s$ 的异或最大值，把这个值丢到大根堆中。
- 查询时每次取出堆顶作为答案，记当前堆顶是对应 $s_i$ 两两异或第 $\mathrm{rnk}$ 大值，则将 $\mathrm{rnk}+1$ 大值重新放入堆中。
这样就过了这道题，时间复杂度为 $O(n\log n\log V)$。
花絮
P6072 Path
定义树上一段路径的权值是这段路径上边权的异或和，你需要求出任意两条点集不交的路径的权值之和的最大值。$n\le3\times10^4$。
将路径异或和转化为异或深度异或和。
首先有一个 observation 是对于一个合法的路径选择，一定存在一个点 $u$ 满足一条路径完全位于 $u$ 子树内，另一条完全在 $u$ 子树外。
那么一个暴力的思想就是枚举子树根，对子树内外分别建 01-trie，然后分别求两两异或最大值。这样时间复杂度是 $O(n^2)$ 的。
我们将树拍扁成 dfn 序，发现如果一个子树的起止是 $l_u,r_u$，那么我们要建出 $[l_u,r_u]$ 和 $[1,l_u)\cup(r_u,n]$。当然我们如果复制数列就是建出 $[l_u,r_u]$ 和 $[r_u+1,l_u+n-1]$ 两个区间的 01-trie 并维护两两异或最大值。
观察数据范围，发现时间复杂度内可以有根号，考虑使用莫队，即有 $2n$ 次查询区间两两异或最大值。发现这个维护加数很简单，但是删除却有难度，考虑使用只加不减的回滚莫队维护，就做完了，时间复杂度 $O(n\sqrt n\log n)$。
回滚莫队代码：
1 | sort(q+1,q+2*n+1,cmp); |