CODEWITHSUNDEEP
algorithmxorsegment-treebitwise-xor
unglinh279
unglinh279

Reputation: 673

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:

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)

Upvotes: 2

Views: 2312

Answers (2)

unglinh279
unglinh279

Reputation: 673

Thanks to Maurycyt I have solved the problem. Below is my code in case anyone need it

const int MAX = 1e5 + 5;
const int MAXBIT = 32;
int n, q, num, xor_add;
int arr[MAX], sum[32];

int getSum()
{
    int res = 0;
    for(int i = 0; i < MAXBIT; i++)
        res += sum[i]*(1<<i);
    return res;
}

void updateXor(int x){
    xor_add ^= x;
    for(int i = 0; i < MAXBIT; i++)
        if(x & (1<<i))sum[i] = num - sum[i];
}

void add(int x){
    ++num;
    arr[n++] = x;
    for(int i = 0; i < MAXBIT; i++)
        if(x & (1<<i))sum[i]++;
}

void remv(int i){
    --num;
    int x = arr[i-1]^xor_add;
    for(int i = 0; i < MAXBIT; i++)
        if(x & (1<<i))sum[i]--;
}

int main()
{
    cin >> n >> q;
    num = n;
    for(int i = 0; i < n; i++)cin >> arr[i];

    for(int i = 0; i < MAXBIT; i++)
        for(int j = 0; j < n; j++)
            if(arr[j] & (1<<i))sum[i]++;

    while(q--){
        int id, x;
        cin >> id >> x;

        if(id == 1)add(x);
        else if(id == 2)remv(x);
        else updateXor(x);

        cout << getSum() << '\n';
    }
    return 0;
}

Upvotes: 2

Maurycyt
Maurycyt

Reputation: 718

Assuming your numbers do not exceed some standard constant like 232 or 264, 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.

Upvotes: 5

Related Questions