 # GEHA1803 - Editorial

Practice

Contest

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;
int cnt;
}
```

\$child\$ and \$child\$ 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\$ .
• 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\$ .
• 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\$ .
• 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\$ .
Current Bit will initially be equal to \$32\$ (depending upon the implementation of your trie) and each time we move to a subtree we will decrement the value of Current Bit by 1 . We will continue this process until the value of Current Bit is greater than or equal to \$0\$ . ## Time Complexity Time complexity of the above solution is \$O(Nlog(n))\$ pre-processing and \$O(log(n))\$ per query . Hence total time complexity will be \$O(Nlog(n)+Qlog(n))\$ ## AUTHOR'S AND TESTER'S SOLUTIONS: Setter's solution Tester's solution Feel free to comment if you have any doubt .
//