Xor of numbers in a range

Question

I just came across a question which goes like this

Given an array of n elements , there are m queries of type l,r,t where in the program must take out xor of all numbers less than t and between index l,r (both inclusive and 0-indexed) .

Example : Say arr={2,3,5,1} Our query is : 0 2 4 Output 1

I can only think of the naive solution of going through the range and just taking the xor of all the numbers less than t but I was just wondering is there any data structure like segment trees which could achieve the task in an efficient manner ?

Answer 1

Here's a solution:

1. Save all the numbers with its index and sort them according to their values (let's call it an array a).

2. First save all the queries with query id and sort them according to t (let's call it an array q).

3. Take a segment tree where every node contains 0 by default. It is a segment tree that contains xor in range.

4. Iterate over q and add all the numbers from a in the segment tree those are less than t for each query and take the xor in the given query range of that and save it to an array using query id (let's all it ans).

5. Print the ans array.

Complexity of this solution is O(nlog(n) + mlog(n)).