01trie

01 trie树

类似于字典树的做法，将每一个数化为二进制数，看作01串，插入到字典树中。如图1：

典型例题

给一个长为$n$的数列，要求一个 $a_i$，$a_j$ ，使得 $a_i$^$a_j$ 最大。

异或的一些性质

• 0^1=1
• 1^1=0
• 0^0=0
• p^p=0
• p^0=1
• 自反性：a^b=c，b^c=a

问题解答

首先建好01trie树，以图1为例，然后对于每一个数，在树上跑一遍贪心，即贪心选择与这个数当前位不同的那个节点。

也就是说，尽可能地保证越高的位的异或和为1，（因为高位的一个1比后面的位全为1都要大）

比如对于7，在下面这个插入了0，2，7的树上跑。
开始在0号节点，然后看最高位，7的最高位是1，所以为了保证当前位异或和为1，应走0的方向，也就是走到1节点。
然后看次高位，7的次高位为1，同理，走0的方向到3号节点，依次类推，得出与7异或的最大值为7。

两道拓展例题

1.第k大异或和

题意：还是给出长为$n$的序列，这次不求最大值了，求第$k$大的$a_i$^$a_j$。

做法：考虑二分答案，对于每个二分到的值$x$，遍历数组跑一遍01trie树，看有多少组异或和是大于$x$的，然后根据大于$x$的异或和的组数向上向下二分。

如何计算大于$x$的组数？

遍历数组，对于每一个数$a_i$,跑一遍01trie，记录比$x$大的异或和的组数$ans$。对于$x$的每一位，若为1，则走树上与$a_i$当前位相反的位置，若为0，则走树上与$a_i$当前位相同的位置，并将与$a_i$当前位相反的那个位置的子树大小加到$ans$中。

由于每一组大于$x$的二元组都会被计算两次，所以最终的$ans$还要除以二。

复杂度$O(nlogn)$。

2.树上的最大异或路径和

题意：给定一棵$n$个点的带权树，寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

做法：观察得到，从$i$~$j$的路径的异或值为$i$到根的异或和^$j$到根的异或和。

因此将例题中的$a_i$转化成节点$i$到根的异或和的值，就可以照着例题的方法做了。

复杂度$O(nlogn)$。