XOR of Numbers that Appeared Even Number of Times in Given Range

Approach

Observation: The answer to the query is:

queryAns = (XOR-sum of all number between{L to R}) ^ (XOR-sum of distinct numbers between{L to R})

We need to find the XOR-sum of numbers that appeared an even number of times in a given range. Two important properties of XOR are (a^a=0) and (a^0=a). 

Here XOR-sum of all numbers will give the XOR of all numbers that appeared an odd number of times in the range {L to R} (Because even times occurring elements will cancel out due to a^a=0 property). 

And XORing this all numbers that appeared an odd number of times with all distinct numbers in that range will give us numbers that appeared an even number of times (this time odd time appearing elements will cancel out).

Efficient: XOR-sum of all numbers in the query range can be calculated using the prefix Xor-sums. And xor-sum of all distinct numbers in a range can be found by using Binary Indexed Tree through the following steps:

i)   Create an array lastOccured[ ] and initialize it with -1. Here lastOccured[a[i]] holds the rightmost index of the number a[i] in the array ‘a’.

ii)  Sort all queries according to the right index ‘R’ in ascending order.

iii) Create a BIT[ ] array and initialize it with all 0s (Binary Indexed Tree).

iv) Iterate over the input array. Also, keep a pointer for queries.

a. Check a[i] has been visited earlier i.e, if lastOccured[a[i]] == -1 or not. If not, update Binary Indexed Tree at the index lastOccured[a[i]] with value -1.

b. Update lastOccured[a[i]] = i and update Binary Indexed Tree at the index i with value a[i].

c. Now answer queries where R = i by using querying Binary Indexed Tree.

Program

#include <bits/stdc++.h>
using namespace std;
 
#define MAXSIZE 1000001
 
// For storing queries.
typedef struct {
    int L;
    int R;
    int idx;
} query;
 
 
// Custom comparator to sort queries in
// ascending order according to R.
bool CustomComparator(query &a, query &b){
    if(a.R == b.R)
        return a.L < b.L;
   
    return a.R < b.R;
}
 
 
/*--------------- BINARY INDEXED TREE. //BEGINS -----------*/
vector<int>BIT;
 
/**
 * @brief This is a utility function which calculate
 * the sum of array[0 ... idx] using the BIT data structure.
 *
 * @param idx Index tree node.
 * @return int
 */
int Sum(int idx){
    int _sum = 0;
 
    /* Traversing the ancestors of idx node. */
    while(idx > 0){
        _sum ^= BIT[idx]; // Add current element in count.
 
        idx -= (idx & -idx); // Move to 'sum' parent node.
    }
    // Return count of smaller element on the right side.
    return _sum;
}
 
/**
 * @brief This function updates a node of Binary Indexed Tree(BIT)
 * at given index 'idx'. Given value 'change' is added to BIT[idx] node
 * and its ancestors.
 *
 * @param idx Index tree node.
 * @param change Effective difference that needs to be updated.
 * @return void
 */
void Update(int idx, int change){
 
    /* Traverse over all ancestors of BIT[idx] and add 'change' */
    while(idx < BIT.size()){    
        BIT[idx] ^= change; // Add 'change' in current node.
 
        idx += (idx & -idx); // Move to 'update' parent node.
    }
}
/*--------------- BINARY INDEXED TREE. //ENDS   -----------*/
 
 
void solve(vector<int> &a, int N, query queries[], int Q){
    // Initialize BIT.
    BIT.clear();
    BIT.resize(N+1, 0);
 
    // Array for storing prefix XOR sums.
    int prefixXOR[N+1];
    memset(prefixXOR, 0, sizeof(prefixXOR));
 
    /* for coordinate compression (because the number can be very
    large but we have limited space.)*/
    map<int, int>mp;
 
    for(int i=0; i<N; i++){
        // Update in map if a[i] has not appeared yet.
        if(!mp[a[i]])
            mp[a[i]] = i;
 
        // pre-calculating prefix XOR sums;
        if(i == 0)
            prefixXOR[i] = a[i];
        else  
            prefixXOR[i] = prefixXOR[i-1] ^ a[i];
    }
 
    /* Array to store last occurence of a[i] */
    int lastOcc[MAXSIZE];
    memset(lastOcc, -1, sizeof(lastOcc));
 
    /* Sort the queries in ascending order according to R */
    sort(queries, queries+Q, CustomComparator);
 
    // To store the final answer for each query.
    int finalAns[Q];
 
    // will be used as a query counter.
    int j = 0;
 
    for(int i=0; i<Q; i++){
 
        while(j <= queries[R]){
            /* If lastOcc[mp[a[j]] is not -1, set null
            in a[j] by xoring it with itself at the
            idx equal lastOcc[mp[a[j]] */
            if(lastOcc[mp[a[j]]] != -1)
                Update(lastOcc[mp[a[j]]]+1, a[j]);
           
            /* Updating the BIT array and setting
            lastOcc[mp[a[j]]] as j */
            Update(j+1, a[j]);
            lastOcc[mp[a[j]]] = j++;
        }
 
        /* Calculate the XOR-sum of all element within the
        range of query using precomputed prefix XORsums */
        int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
 
        /* Calculate the XOR-sum of distinct elements within the
        range of query using Binary Indexed Tree */
        int distinctXOR = Sum(queries[i].R+1) ^ Sum(queries[i].L);
 
        // Save the answer.
        finalAns[queries[i].idx] = allXOR ^ distinctXOR;
    }
 
    // Print final answers.
    for(int i=0; i<Q; i++)
        cout << finalAns[i] << endl;
}
 
// Driver Function.
int main(){
    int tt = 1;
    cin >> tt;
    while(tt--){
        int N; cin >> N;
 
        vector<int>a(N);
        for(int i=0; i<N; i++)cin >> a[i];
 
        int Q; cin >> Q;
        query queries[Q];
        for(int i=0; i<Q; i++){
            cin >> queries[i].L >> queries[i].R;
            queries[i].idx = i;
        }
 
        solve(a, N, queries, Q);
    }
    return 0;
}

INPUT

1
7
1 2 1 3 3 2 3
5
3 6
3 4
0 2
0 6
0 4

OUTPUT

0
3
1
3
2

Time Complexity

The time complexity of the above approach is O(Q * log(N)), where Q is the number of queries and N is the size of the input array.

Space Complexity

The auxiliary space complexity of the program is O(N).

Check out this problem - Count Inversions

FAQs

1. What is Fenwick Tree or Binary Indexed Tree?
   A Fenwick tree or Binary Indexed Tree is a data structure that allows efficient calculations of prefix sums and efficient updates of elements in the array (while retaining tree structure & all its properties). 
    
2. What is the time complexity of insertion and query in a Fenwick Tree or Binary Indexed Tree?
   The time complexity of insertion and deletion in a Binary Indexed Tree containing N elements is O(logN).
    
3. What is the advantage of Fenwick tree over Segment tree?
   The main advantage of the Fenwick tree is that it requires less space, is relatively simple to implement, and has concise code.
    
4. What is the disadvantage of the Fenwick tree over the Segment tree?
   We can only use the Fenwick tree in queries where L=1. Therefore it cannot solve many problems.

Key Takeaways

Cheers if you reached here!! 

This article discussed an intriguing problem using the Fenwick Tree or Binary Indexed Tree. Fenwick Tree-based problems are sometimes simple to implement, but finding an efficient approach remains difficult.

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!