algorithm - 如何有效地将 XOR 应用于两个整数数组？

Question

我有两个数组如下:

A = [1,2,35,4,32,1,2,56,43,2,21]
B = [1,2,35,4,32,1,2,56,43,45,1]

正如我们所见，A 和 B 在第 43 个元素之前具有相同的初始子序列。我的最终目标是计算这两个序列的最后一个不常见元素的异或。在这里，我的目标是找到 {2,21,45,1} 的 XOR。

目前，我的方法是将这两个数组的运行 XOR 存储在两个单独的数组(比如 RESA[]，& RESB[])中，然后每当我被要求找到 A[0- 的 XOR 10] & B[0-9]，我只是快速执行了一次异或运算如下:

RESA[10] ^ RESB[9]

这是有效的，因为在进行异或运算时，公共(public)元素会相互抵消。

我的问题是，如果在每个查询中都超过阈值 T 会怎样。例如，在这种情况下，如果传递的阈值是 32，我必须过滤 A 和 B 中小于 32 的元素，然后对所有这些元素应用 XORing。这无疑增加了复杂性，我无法应用我之前保持运行元素异或的逻辑。

如果您对如何利用 XOR 属性在没有阈值的情况下像以前一样提出恒定时间方法有任何想法，请告诉我。

Answer 1

您已经工作过，您可以通过计算两个数组中每个元素的异或来找到不常见元素的异或。

XOR 是一个交换和结合运算符，因此我们可以以任何我们喜欢的方式重新排序数组，并且仍然具有相同的总 XOR。

特别是，我们可以对每个数组进行反向排序，然后计算每个排序数组的运行异或。

通过这种预处理，我们现在可以通过对每个排序数组使用二进制搜索来计算高于阈值的所有元素的异或，以查找高于 T 的元素数量，然后查找正在运行的异或数组。

这为每个查询提供了 O(logn) 的复杂度。

扩展

上面的答案假设查询只是阈值 32:即开始总是 0，结束总是每个序列的长度。 (我这么认为是因为问题说最终目标是计算所有不常见元素的异或。)

如果查询还包含要进行异或运算的区域的开始和结束，我会建议使用需要更多存储空间的不同方法(因为它需要对所有查询进行缓冲和排序):

1. 按阈值对所有查询进行排序
2. 为每个序列维护异或的线段树，初始化为0。
3. 按降序将值添加到序列中，并在插入所有高于阈值的值后立即执行查询。

例如，序列 C=[1,2,35,4,32,1,2,56] 的线段树将包含:

1
2
35
4
32
1
2
56
1^2
35^4
32^1
2^56
1^2^35^4
32^1^2^56
1^2^35^4^32^1^2^56

一旦我们有了这些值，我们就可以使用 log(n) 步计算任何范围的 XOR。例如，假设我们想要计算 C[1:3] = [2,35,4] 的 XOR。我们可以通过将 2 与 35^4 进行异或来实现。