对给定数组的XOR查询
给定一个包含 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} -> sum = 37
2 2 -> arr[] = {7, 12, 0, 3, 3, 6} -> sum = 31
3 2 -> arr[] = {5, 14, 2, 1, 1, 4} -> sum = 27
2 7 -> arr[] = {5, 14, 2, 1, 1} -> sum = 23
P/S：我正在尝试使用 Segment Tree 解决问题，但我无法使用 XOR 运算符更新树。有没有其他方法可以解决这个问题？我试图在 O(n.logn) 中解决它
回答
假设您的数字不超过一些标准常数，如 2 32或 2 64，我们可以在恒定时间内通过分别计算位来做到这一点。
您将需要：
- 记住数组中有多少个数字
- 记住二进制定位系统中每个位置有多少点亮位。
所以这是您的示例，扩展为位，最不重要的位于顶部：
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（现在^我的意思是取幂而不是异或）。
所以这就是你每次弹出 xor 操作时所做的。添加和删除数字是很容易的部分，因为您会检查它们的位并相应地调整i数组中点亮的“ -th”位的计数。