algorithm - 对给定数组进行 XOR 查询

Question

给定一个包含 n 个整数的数组，索引从 1->n。任务是执行 Q 个给定的查询，并打印每次查询后数组的总和。

我们可以执行三种类型的操作:

• 1 X:将 X 添加到数组中(其索引将为 n+1，n+2，...)
• 2 Y:从数组中移除索引为Y的元素
• 3 Z:对数组中的每个元素i，执行i^Z (i xor Z)

示例:

输入

arr[] = {2, 3, 9, 5, 6, 6}, Q = 5
1 3
3 5
2 2
3 2
2 7

输出: 34 37 31 27 23

解释:

1 3 -> arr[] = {2, 3, 9, 5, 6, 6, 3} -> 总和 = 34

3 5 -> arr[] = {7, 6, 12, 0, 3, 3, 6} -> 总和 = 37

2 2 -> arr[] = {7, 12, 0, 3, 3, 6} -> 总和 = 31

3 2 -> arr[] = {5, 14, 2, 1, 1, 4} -> 总和 = 27

2 7 -> arr[] = {5, 14, 2, 1, 1} -> 总和 = 23

P/S: 我正在尝试用线段树解决问题，但我无法用 XOR 运算符更新树。还有其他方法可以解决这个问题吗？我试图在 O(n.logn) 中解决它

Answer 1

假设您的数字不超过某个标准常量，例如 2³² 或 2⁶⁴，我们可以通过分别计算位来在恒定时间内做到这一点。

你需要:

1. 记住数组中有多少个数
2. 记住二进制定位系统中每个位置有多少个点亮的位。

所以这是你的例子，扩展成位，最不重要的位在顶部:

2  3  9  5  6  6  3 | sum
-------------------------
0  1  1  1  0  0  1 | 4
1  1  0  0  1  1  1 | 5
0  0  0  1  1  1  0 | 3
0  0  1  0  0  0  0 | 1

现在，这意味着有

• 4 “第一”位点亮
• 5 “第二”位点亮
• 3 “第三”位点亮并且
• 1“第四”位点亮。
• 数字的个数是7。
• 这些数字的总和是34

我们现在用 5 对它进行异或，它是二进制的 0101，所以现在会有

• 7 - 4 = 3 “第一”位点亮
• 5 “第二”位点亮
• 7 - 3 = 4 “第三”位点亮
• 1 “第四”位点亮

如果我们总结一下，我们得到 3 * 2^0 + 5 * 2^1 + 4 * 2^2 + 1 * 2^3 = 37(现在 ^ 我的意思是求幂而不是异或)。

所以这就是每次弹出异或运算时你要做的。添加和删​​除数字是比较容易的部分，因为您遍历它们的位并相应地调整数组中点亮的“i-th”位的计数。