## 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]$ .