Range Query on array whose each element is XOR of index value and previous element

Consider an arr[] which can be defined as: 

You are given Q queries of the form [l, r]. The task is to output the value of arr[l] ? arr[l+1] ? ..... ? arr[r-1] ? arr[r] for each query.

Examples : 

Input : q = 3 q1 = { 2, 4 } q2 = { 2, 8 } q3 = { 5, 9 } Output : 7 9 15 The beginning of the array with constraint look like: arr[] = { 0, 1, 3, 0, 4, 1, 7, 0, 8, 1, 11, .... } For q1, 3 ? 0 ? 4 = 7 For q2, 3 ? 0 ? 4 ? 1 ? 7 ? 0 ? 8 = 9 For q3, 1 ? 7 ? 0 ? 8 ? 1 = 15

Let's observe arr[] 

arr[0] = 0 arr[1] = 1 arr[2] = 1 ? 2 arr[3] = 1 ? 2 ? 3 arr[4] = 1 ? 2 ? 3 ? 4 arr[5] = 1 ? 2 ? 3 ? 4 ? 5 ....

Let's make another array, say brr[], where brr[i] = arr[0] ? arr[1] ? arr[2] ? ..... ? arr[i]. 
brr[i] = arr[0] ? arr[1] ? arr[2] ? ... ? arr[i-1] ? arr[i] = brr[j] ? arr[j+1] ? arr[j+2] ? ..... ? arr[i], for any 0 <= j <= i. 
So, arr[l] ? arr[l+1] ? ..... ? arr[r] = brr[l-1] ? brr[r].

Now, let's observe brr[]: 

brr[1] = 1 brr[2] = 2 brr[3] = 1 ? 3 brr[4] = 2 ? 4 brr[5] = 1 ? 3 ? 5 brr[6] = 2 ? 4 ? 6 brr[7] = 1 ? 3 ? 5 ? 7 brr[8] = 2 ? 4 ? 6 ? 8

It's easy to observe that in odd indexes brr[i] = 1 ? 3 ? 5 ? .... ? i and for even indexes brr[i] = 2 ? 4 ? 6 ? .... ? i.
For even indexes there are numbers from 1 to i/2 multipliedby 2, that means bits are moved to left by 1, so, brr[i] = 2 ? 4 ? 6 ? .... ? i = (1 ? 2 ? 3 ? ..... ? i/2) * 2. 
And for odd indexes there are numbers from 0 to (i - 1)/2 multiplied by 2 and plus 1. That means bits are moved to left by 1, and last bit is made 1. So, brr[i] = 1 ? 3 ? 5 ? .... ? i = (0 ? 1 ? 2 ? .... ? (i - 1)/2) * 2 + x. 
x is 1 ? 1 ? 1 ? ..... ? 1 "ones" are repeated (i - 1)/2 + 1 times. So, if (i-1)/2 + 1 is odd then x = 1 else x = 0.
Now, calculation of 1 ? 2 ? 3 ? .... ? x. 

Let's prove that (4K) ? (4K + 1) ? (4K + 2) ? (4K + 3) = 0 for 0 <= k. 

 bitmask(K)00=4K xorsum bitmask(K)01=4K+1 bitmask(K)10=4K+2 bitmask(K)11=4k+3 --------------------- 000000000000=0

So as 0 ? Y = Y then 1 ? 2 ? 3 ? ... ? x = (floor(x/4) x 4) ? ... ? x here are maximum 3 numbers so we can calculate in O(1).

Below is the implementation of this approach:

// CPP Program to solve range query on array // whose each element is XOR of index value // and previous element. #include <bits/stdc++.h> using namespace std; // function return derived formula value. int fun(int x) {  int y = (x / 4) * 4;  // finding xor value of range [y...x]  int ans = 0;  for (int i = y; i <= x; i++)  ans ^= i;  return ans; } // function to solve query for l and r. int query(int x) {  // if l or r is 0.  if (x == 0)  return 0;  int k = (x + 1) / 2;  // finding x is divisible by 2 or not.  return (x %= 2) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } void allQueries(int q, int l[], int r[]) {  for (int i = 0; i < q; i++)  cout << (query(r[i]) ^ query(l[i] - 1)) << endl; } // Driven Program int main() {  int q = 3;  int l[] = { 2, 2, 5 };  int r[] = { 4, 8, 9 };  allQueries(q, l, r);  return 0; } 

// Java Program to solve range query on array // whose each element is XOR of index value // and previous element. import java.io.*; class GFG {    // function return derived formula value.  static int fun(int x)  {  int y = (x / 4) * 4;    // finding xor value of range [y...x]  int ans = 0;    for (int i = y; i <= x; i++)  ans ^= i;    return ans;  }    // function to solve query for l and r.  static int query(int x)  {    // if l or r is 0.  if (x == 0)  return 0;    int k = (x + 1) / 2;    // finding x is divisible by 2 or not.  return ((x %= 2) != 0) ? 2 * fun(k) :   ((fun(k - 1) * 2) ^ (k & 1));  }    static void allQueries(int q, int l[], int r[])  {  for (int i = 0; i < q; i++)  System.out.println((query(r[i]) ^   query(l[i] - 1))) ;  }    // Driven Program  public static void main (String[] args) {    int q = 3;  int []l = { 2, 2, 5 };  int []r = { 4, 8, 9 };    allQueries(q, l, r);    } } // This code is contributed by vt_m. 

# Python3 Program to solve range query  # on array whose each element is XOR of  # index value and previous element.  # function return derived formula value.  def fun(x): y = (x // 4) * 4 # finding xor value of range [y...x]  ans = 0 for i in range(y, x + 1): ans ^= i return ans # function to solve query for l and r.  def query(x): # if l or r is 0.  if (x == 0): return 0 k = (x + 1) // 2 # finding x is divisible by 2 or not.  if x % 2 == 0: return((fun(k - 1) * 2) ^ (k & 1)) else: return(2 * fun(k)) def allQueries(q, l, r): for i in range(q): print(query(r[i]) ^ query(l[i] - 1)) # Driver Code q = 3 l = [ 2, 2, 5 ] r = [ 4, 8, 9 ] allQueries(q, l, r) # This code is contributed  # by sahishelangia 

// C# Program to solve range query on array // whose each element is XOR of index value // and previous element. using System; class GFG {    // function return derived formula value.  static int fun(int x)  {  int y = (x / 4) * 4;    // finding xor value of range [y...x]  int ans = 0;  for (int i = y; i <= x; i++)  ans ^= i;    return ans;  }    // function to solve query for l and r.  static int query(int x)  {  // if l or r is 0.  if (x == 0)  return 0;    int k = (x + 1) / 2;    // finding x is divisible by 2 or not.  return ((x %= 2)!=0) ? 2 * fun(k) :   ((fun(k - 1) * 2) ^ (k & 1));  }    static void allQueries(int q, int []l, int []r)  {  for (int i = 0; i < q; i++)  Console.WriteLine((query(r[i])   ^ query(l[i] - 1))) ;  }    // Driven Program  public static void Main ()  {  int q = 3;  int []l = { 2, 2, 5 };  int []r = { 4, 8, 9 };    allQueries(q, l, r);    } } // This code is contributed by vt_m. 

<?php // PHP Program to solve range  // query on array whose each  // element is XOR of index  // value and previous element. // function return derived // formula value. function fun($x) { $y = ((int)($x / 4) * 4); // finding xor value  // of range [y...x] $ans = 0; for ($i = $y; $i <= $x; $i++) $ans ^= $i; return $ans; } // function to solve  // query for l and r. function query($x) { // if l or r is 0. if ($x == 0) return 0; $k = (int)(($x + 1) / 2); // finding x is divisible // by 2 or not. return ($x %= 2) ? 2 * fun($k) : ((fun($k - 1) * 2) ^ ($k & 1)); } function allQueries($q, $l, $r) { for ($i = 0; $i < $q; $i++) echo (query($r[$i]) ^ query($l[$i] - 1)) , "\n"; } // Driver Code $q = 3; $l = array( 2, 2, 5 ); $r = array ( 4, 8, 9 ); allQueries($q, $l, $r); // This code is contributed by ajit ?> 

<script> // Javascript Program to solve range query on array // whose each element is XOR of index value // function return derived formula value. function fun(x) {  let y = parseInt(x / 4) * 4;  // finding xor value of range [y...x]  let ans = 0;  for (let i = y; i <= x; i++)  ans ^= i;  return ans; } // function to solve query for l and r. function query(x) {  // if l or r is 0.  if (x == 0)  return 0;  let k = parseInt((x + 1) / 2);  // finding x is divisible by 2 or not.  return (x %= 2) ? 2 * fun(k) : ((fun(k - 1) * 2) ^ (k & 1)); } function allQueries(q, l, r) {  for (let i = 0; i < q; i++)  document.write((query(r[i]) ^ query(l[i] - 1)) + "<br>"); } // Driven Program  let q = 3;  let l = [ 2, 2, 5 ];  let r = [ 4, 8, 9 ];  allQueries(q, l, r); </script> 

0 2 0

Time Complexity: O(q* log(n)) where q is the number of queries and n is the largest value of r in the queries. 

Auxiliary Space: O(1)