PROBLEM LINKS:
DIFFICULTY:
Medium
PREREQUISITES:
Trie and Persistent Data Structures.
PROBLEM:
Given an array of N integers and Q queries where each query contains four integers l r x y find the number of elements in the range l to r whose bitwise xor with x results in a number greater than or equal to y .
QUICK EXPLANATION
Consider a function f(i,x,y) which returns the number of elements in the range 1 to i whose bitwise xor with x is greater than or equal to y . If we can calculate f(i,x,y) for all i then the answer for each query will be f(r,x,y) - f(l-1,x,y). We will use persistent trie to calculate f(i,x,y) efficiently.
EXPLANATION
If you don’t know about persistent data I would recommend reading about it from here before proceeding any further . For the rest of the editorial I would be assuming you know how to create persistent data structures .
Let us denote the the trie formed by elements from 1 to i as root[i] . root[i] can be calculated from root[i-1] in O(log(n)) using the concept of persistent data structures .
Our trie block will be like this:
```
struct Trie
{
Trie *child[2];
int cnt;
}
```
$child[0]$ and $child[1]$ are trie pointers which point to respective subtree of trie depending upon whether corresponding bit is set or unset . $cnt$ stores the number of elements in the subtree of the current trie node . Our problem now reduces to finding the number of elements whose bitwise xor with $x$ is greater than or equal to $y$ in a given trie . Consider the binary representation of $x$ and $y$ , there will be four cases:
- Current bit of $x$ is $1$ and Current bit of $y$ is also $1$ , then all the numbers whose Current bit is $1$ when taken xor with with $x$ will result in a number lesser than $y$ and for all the numbers whose Current bit is $0$ may or may not result in a number greater than or equal to $y$ when taken xor with $x$ so we will move to the subtree of which contains $0$ at the Current bit i.e , $child[0]$ .
- Current bit of $x$ is $0$ and Current bit of $y$ is $1$ , then all the numbers whose Current bit is $0$ when taken xor with $x$ will result in a number lesser than $y$ and for all the numbers whose Current bit is $1$ may or may not result in a number greater than or equal to $y$ when taken xor with $x$ so we will move to the subtree of which contains $1$ at the Current bit i.e , $child[1]$ .
- Current bit of $x$ is $1$ and Current bit of $y$ is $0$ , then all the numbers whose Current bit is $0$ when taken xor with with $x$ will result in a number greater than $y$ so we will directly add the $cnt$ of that subtree in our answer and for all the numbers whose Current bit is $1$ may or may not result in a number greater than or equal to $y$ when taken xor with $x$ so we will move to the subtree of which contains $1$ at the Current bit i.e , $child[1]$ .
- Current bit of $x$ is $0$ and Current bit of $y$ is also $0$ , then all the numbers whose Current bit is $1$ when taken xor with $x$ will result in a number greater than $y$ so we will directly add the $cnt$ of that subtree in our answer and for all the numbers whose Current bit is $0$ may or may not result in a number greater than or equal to $y$ when taken xor with $x$ so we will move to the subtree of which contains $0$ at the Current bit i.e , $child[0]$ .