XOR queries on a given array

Given an array of n integers, indexed from 1->n. The task is to perform of Q given queries, and print the sum of the array after each queries.

We can perform three types of operations:

• 1 X: add X to the array (its index will be n+1, n+2,...)
• 2 Y: remove element with index Y from the array
• 3 Z: for each element i in the array, perform i^Z (i xor Z)

Example:

Input

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

Output: 34 37 31 27 23

Explanation:

1 3 -> arr[] = {2, 3, 9, 5, 6, 6, 3} -> sum = 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: I'm trying to solve the problem with Segment Tree, but I can't update the tree with XOR operator. Is there any other way to solve this problem? I'm trying to solve it in O(n.logn)

Assuming your numbers do not exceed some standard constant like 2³² or 2⁶⁴, we can do this in constant time, by counting the bits separately.

You will need to:

1. Remember how many numbers there are in the array
2. Remember how many lit bits there are at every position in the binary positioning system.

So here's your example, expanded into bits, with the least significant ones at the top:

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

Now, that means that there are

• 4 "first" bits lit
• 5 "second" bits lit
• 3 "third" bits lit and
• 1 "fourth" bit lit.
• The number of numbers is 7.
• The sum of these numbers is 34

We now xor this with 5, which is 0101 in binary, so there will now be

• 7 - 4 = 3 "first" bits lit
• 5 "second" bits lit
• 7 - 3 = 4 "third" bits lit
• 1 "fourth" bit lit

If we sum this up, we get 3 * 2^0 + 5 * 2^1 + 4 * 2^2 + 1 * 2^3 = 37 (where now by ^ I mean exponentiation as opposed to xor).

So this is what you do every time the xor operation pops up. Adding and removing numbers is the easy parts because you go over their bits and accordingly adjust the counts of lit "i-th" bits in the array.