Hello Everyone,
Given an array of numbers of size N and Q queries. Each query or a range can be represented by L (LeftIndex) and R(RightIndex). Find the XOR-sum of the numbers that appeared even number of times in the given range.
Examples :
Input : arr[] = { 1, 2, 1, 3, 3, 2, 3 }
Q = 5
L = 3, R = 6
L = 3, R = 4
L = 0, R = 2
L = 0, R = 6
L = 0, R = 4
Output : 0
3
1
3
2
Explanation of above example:
In Query 1, there are no numbers which appeared even number of times.
Hence the XOR-sum is 0.
In Query 2, {3} appeared even number of times. XOR-sum is 3.
In Query 3, {1} appeared even number of times. XOR-sum is 1.
In Query 4, {1, 2} appeared even number of times. XOR-sum is 1 xor 2 = 3.
In Query 5, {1, 3} appeared even number of times. XOR-sum is 1 xor 3 = 2.
Approach :
Firstly, it is easy to note that the answer for the query is the XOR-sum of all elements in the query range xor-ed with XOR-sum of distinct elements in the query range (since taking XOR of an element with itself results into a null value). Find the XOR-sum of all numbers in query range using prefix XOR-sums.
Now, returning back to our main problem, just change the assignment BIT[i] = 1 to BIT[i] = arri and count the XOR-sum instead of sum.
Below is the implementation using Binary Indexed Trees in CPP
// CPP Program to Find the XOR-sum
// of elements that appeared even
// number of times within a range
#include <bits/stdc++.h>
using
namespace
std;
/* structure to store queries
L --> Left Bound of Query
R --> Right Bound of Query
idx --> Query Number */
struct
que {
int
L, R, idx;
};
// cmp function to sort queries
// according to R
bool
cmp(que a, que b)
{
if
(a.R != b.R)
return
a.R < b.R;
else
return
a.L < b.L;
}
/* N --> Number of elements present in
input array. BIT[0..N] --> Array that
represents Binary Indexed Tree*/
// Returns XOR-sum of arr[0..index]. This
// function assumes that the array is
// preprocessed and partial sums of array
// elements are stored in BIT[].
int
getSum(
int
BIT[],
int
index)
{
// Iniialize result
int
xorSum = 0;
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse ancestors of BIT[index]
while
(index > 0)
{
// Take XOR of current element
// of BIT to xorSum
xorSum ^= BIT[index];
// Move index to parent node
// in getSum View
index -= index & (-index);
}
return
xorSum;
}
// Updates a node in Binary Index Tree
// (BIT) at given index in BIT. The
// given value 'val' is xored to BIT[i]
// and all of its ancestors in tree.
void
updateBIT(
int
BIT[],
int
N,
int
index,
int
val)
{
// index in BITree[] is 1 more than
// the index in arr[]
index = index + 1;
// Traverse all ancestors and
// take xor with 'val'
while
(index <= N)
{
// Take xor with 'val' to
// current node of BIT
BIT[index] ^= val;
// Update index to that of
// parent in update View
index += index & (-index);
}
}
// Constructs and returns a Binary Indexed
// Tree for given array of size N.
int
* constructBITree(
int
arr[],
int
N)
{
// Create and initialize BITree[] as 0
int
* BIT =
new
int
[N + 1];
for
(
int
i = 1; i <= N; i++)
BIT[i] = 0;
return
BIT;
}
// Function to answer the Queries
void
answeringQueries(
int
arr[],
int
N,
que queries[],
int
Q,
int
BIT[])
{
// Creating an array to calculate
// prefix XOR sums
int
* prefixXOR =
new
int
[N + 1];
// map for coordinate compression
// as numbers can be very large but we
// have limited space
map<
int
,
int
> mp;
for
(
int
i = 0; i < N; i++) {
// If A[i] has not appeared yet
if
(!mp[arr[i]])
mp[arr[i]] = i;
// calculate prefixXOR sums
if
(i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] =
prefixXOR[i - 1] ^ arr[i];
}
// Creating an array to store the
// last occurrence of arr[i]
int
lastOcc[1000001];
memset
(lastOcc, -1,
sizeof
(lastOcc));
// sort the queries according to comparator
sort(queries, queries + Q, cmp);
// answer for each query
int
res[Q];
// Query Counter
int
j = 0;
for
(
int
i = 0; i < Q; i++)
{
while
(j <= queries[i].R)
{
// If last visit is not -1 update
// arr[j] to set null by taking
// xor with itself at the idx
// equal lastOcc[mp[arr[j]]]
if
(lastOcc[mp[arr[j]]] != -1)
updateBIT(BIT, N,
lastOcc[mp[arr[j]]], arr[j]);
// Setting lastOcc[mp[arr[j]]] as j and
// updating the BIT array accordingly
updateBIT(BIT, N, j, arr[j]);
lastOcc[mp[arr[j]]] = j;
j++;
}
// get the XOR-sum of all elements within
// range using precomputed prefix XORsums
int
allXOR = prefixXOR[queries[i].R] ^
prefixXOR[queries[i].L - 1];
// get the XOR-sum of distinct elements
// within range using BIT query function
int
distinctXOR = getSum(BIT, queries[i].R) ^
getSum(BIT, queries[i].L - 1);
// store the final answer at the numbered query
res[queries[i].idx] = allXOR ^ distinctXOR;
}
// Output the result
for
(
int
i = 0; i < Q; i++)
cout << res[i] << endl;
}
// Driver program to test above functions
int
main()
{
int
arr[] = { 1, 2, 1, 3, 3, 2, 3 };
int
N =
sizeof
(arr) /
sizeof
(arr[0]);
int
* BIT = constructBITree(arr, N);
// structure of array for queries
que queries[5];
// Intializing values (L, R, idx) to queries
queries[0].L = 3;
queries[0].R = 6, queries[0].idx = 0;
queries[1].L = 3;
queries[1].R = 4, queries[1].idx = 1;
queries[2].L = 0;
queries[2].R = 2, queries[2].idx = 2;
queries[3].L = 0;
queries[3].R = 6, queries[3].idx = 3;
queries[4].L = 0;
queries[4].R = 4, queries[4].idx = 4;
int
Q =
sizeof
(queries) /
sizeof
(queries[0]);
// answer Queries
answeringQueries(arr, N, queries, Q, BIT);
return
0;
}
Output:
0 3 1 3 2
Time Complexity: O(Q * Log(N)), where N is the size of array, Q is the total number of queries.