如何有效地将 XOR 应用于两个整数数组？
How to efficiently apply XOR to two integer arrays?
我有两个数组如下：
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-10] & B[0-9] 的异或，我只是快速执行一次异或操作如下：
RESA[10] ^ RESB[9]
这是可行的，因为在进行异或运算时，公共元素会抵消。
我的问题是，如果在每个查询中都超过了一个阈值 T。例如，在这种情况下，如果传递的阈值是 32，我必须过滤 A 和 B 中小于 32 的元素，然后对所有这些元素应用 XORing。这肯定会增加复杂性，我无法应用我之前保持元素的 运行 异或的逻辑。
如果您对如何利用 XOR 属性在没有阈值的情况下像以前一样提出恒定时间方法有任何想法，请告诉我。
你已经工作过，你可以通过计算两个数组中每个元素的异或来找到不常见元素的异或。
XOR 是一个交换和结合运算符，因此我们可以按照我们喜欢的任何方式重新排序数组，并且仍然具有相同的总 XOR。
特别是，我们可以对每个数组进行反向排序，然后计算每个排序数组的 运行 异或。
通过这种预处理，我们现在可以通过对每个排序数组使用二进制搜索来计算高于阈值的所有元素的异或，以查找高于 T 的元素数量，然后查找 运行 异或数组。
每个查询的复杂度为 O(logn)。
扩展
上面的答案假设查询只是阈值32：即开始总是0，结束总是每个序列的长度。 （我这么认为是因为问题说最终目标是计算所有不常见元素的异或。）
如果查询还包含要进行异或运算的区域的开始和结束，我建议使用需要更多存储空间的不同方法（因为它需要对所有查询进行缓冲和排序）：
- 按阈值对所有查询进行排序
- 为每个序列维护一个异或的线段树，初始化为0。
- 按降序将值添加到序列中，并在插入所有高于阈值的值后立即执行查询。
例如，序列 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 进行异或来实现。
我有两个数组如下：
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 存储在两个单独的数组（例如，RESA[]，& RESB[]）中，然后每当我被要求找到A[0-10] & B[0-9] 的异或，我只是快速执行一次异或操作如下：
RESA[10] ^ RESB[9]
这是可行的，因为在进行异或运算时，公共元素会抵消。
我的问题是，如果在每个查询中都超过了一个阈值 T。例如，在这种情况下，如果传递的阈值是 32，我必须过滤 A 和 B 中小于 32 的元素，然后对所有这些元素应用 XORing。这肯定会增加复杂性，我无法应用我之前保持元素的 运行 异或的逻辑。
如果您对如何利用 XOR 属性在没有阈值的情况下像以前一样提出恒定时间方法有任何想法，请告诉我。
你已经工作过，你可以通过计算两个数组中每个元素的异或来找到不常见元素的异或。
XOR 是一个交换和结合运算符，因此我们可以按照我们喜欢的任何方式重新排序数组，并且仍然具有相同的总 XOR。
特别是，我们可以对每个数组进行反向排序，然后计算每个排序数组的 运行 异或。
通过这种预处理，我们现在可以通过对每个排序数组使用二进制搜索来计算高于阈值的所有元素的异或，以查找高于 T 的元素数量，然后查找 运行 异或数组。
每个查询的复杂度为 O(logn)。
扩展
上面的答案假设查询只是阈值32：即开始总是0，结束总是每个序列的长度。 （我这么认为是因为问题说最终目标是计算所有不常见元素的异或。）
如果查询还包含要进行异或运算的区域的开始和结束，我建议使用需要更多存储空间的不同方法（因为它需要对所有查询进行缓冲和排序）：
- 按阈值对所有查询进行排序
- 为每个序列维护一个异或的线段树，初始化为0。
- 按降序将值添加到序列中，并在插入所有高于阈值的值后立即执行查询。
例如，序列 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 进行异或来实现。