从数组中找到具有最大异或的子数组（使用特里树）

Question

问题陈述是：

给定一个整数数组，找到具有最大异或的子数组。

一些例子是：

Input: arr[] = {1, 2, 3, 4}
Output: 7
The subarray {3, 4} has maximum XOR value

Input: arr[] = {8, 1, 2, 12, 7, 6}
Output: 15
The subarray {1, 2, 12} has maximum XOR value

我找到了一个quora 帖子，它提供了对问题解决方案的解释，但我不太能完全理解所解释的内容。

该帖子首先介绍了一个与上述问题类似的问题（帖子中的问题 1）：

给定一个整数数组，我们必须找到 XOR 最大的两个元素

然后它描述了一个可以处理两种类型查询的 trie 数据结构：

1. 插入一个数字 X
2. 给定一个 Y，找出 Y 与迄今为止插入的所有数字的最大异或。如果我们有这个数据结构，我们将随时插入整数，并且使用第二类型的查询我们将找到最大的 XOR

上图处理查询类型 1。对于查询类型 2，帖子具有以下内容：

假设我们的数字 Y 是 b1,b2...bn，其中 b1,b2.. 是二进制位。我们从 b1 开始。现在为了使 XOR 达到最大值，我们将在进行 XOR 之后尝试使最高有效位为 1。所以，如果 b1 是 0，我们需要一个 1，反之亦然。在 trie 中，我们转到所需的位侧。如果没有有利的选择，我们就去另一边。对 i=1 到 n 重复此操作，我们将获得可能的最大 XOR。

这里有几个混淆点。一个是：trie 究竟是如何用于查找到数组中的当前点具有最大 XOR 的两个元素的？他们似乎在说这样的话：

例如array= {1,2,3,4}，当前数字是 3 -> 0011（4 位表示）意味着 1 和 2 已经插入到树中。到目前为止，最大异或应该是数字 1 和 2（产生 3）。使用帖子中提供的方法，似乎可以将最大异或存储在一个变量中，以便在数组中的最后一个数字与特里树的当前统计数据进行异或时（我假设它会有元素1,2 和 3 已经插入），该变量将具有到目前为止的最大值。但是算法将如何存储哪两个元素已被异或以产生最大值？

最后，应该将这种方法的逻辑应用于问题（帖子中的问题2）：

给定一个整数数组，找到具有最大异或的子数组

在这里，提供了以下解决方案：

假设 F(L,R) 是从 L 到 R 的子数组的 XOR。这里我们使用 F(L,R)=F(1,R) XOR F(1,L-1) 的性质。如何？假设我们的具有最大异或的子数组在位置 i 结束。现在，我们需要最大化 F(L,i) 即。F(1,i) XOR F(1,L-1) 其中 L<=i。假设，我们将 F(1,L-1) 插入到我们的所有 L<=i 中，那么这就是问题 1。

我不太明白 F(L,R)=F(1,R) XOR F(1,L-1) 的性质。我在这里假设 R 是最大子数组的右边界，而 L 将是它的左边界，但不清楚为什么 F(1,i) 需要与 F(1,L-1) 进行异或. 由此，问题 1 的逻辑将如何应用于这里？

我意识到这个问题很长，但由于问题是多方面的，似乎有必要包括问题的这些基本部分。

Answer 1

第一个问题：当你将一个元素添加到一个 trie 中时，你可以在叶子中存储额外的信息，指示该元素在数组中的索引。当您遍历 trie 并到达一个使 xor 最大化的叶子时Y（如您的问题中所述），您可以将两个索引与最大值一起记录（的索引Y称为您要添加的元素）。

这里f(l, r) = f(0, r) ^ f(0, l - 1)证明了等式。

一旦我们有了这个等式和第一个问题的解决方案（上面描述的稍微修改以记录索引），我们立即得到第二个问题的解决方案。如何？我们可以计算f(i)所有有效值i，然后运行这个算法来得到两个最大化 xor 的索引。让他们成为L和R，在哪里L < R。那么答案就是[L + 1, R]子数组。