>我有两个数组如下：
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] 的 XOR 时，我只需快速执行单个 XOR 操作，如下所示：
RESA[10] ^ RESB[9]
这是有效的，因为在异或时，公共元素会抵消。
我的问题是，如果在每个查询中都通过了阈值 T，该怎么办。例如，在这种情况下，如果传递的阈值32则 I 必须过滤 A 和 B 中都小于 32 的元素，然后对所有此类元素应用 XOR 运算。这肯定会增加复杂性，我无法应用我之前继续运行元素 XOR 的逻辑。
如果您对如何利用 XOR 属性提出像以前没有阈值时一样的恒定时间方法有任何想法，请告诉我。
您已经通过计算两个数组中每个元素的 XOR 来找到不常见元素的 XOR。
XOR 是一个交换和关联运算符，因此我们可以以我们喜欢的任何方式对数组进行重新排序，并且仍然具有相同的总 XOR。
特别是，我们可以对每个数组进行反向排序，然后计算每个排序数组的运行 XOR。
通过这种预处理，我们现在可以通过对每个排序数组使用二叉搜索来计算高于阈值的所有元素的 XOR，以查找高于 T 的元素数量，然后查找正在运行的 XOR 数组。
这为每个查询提供了 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] 的异或。 我们可以通过 35^4 的 xoring 2 来做到这一点。