text: 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:
  C++
  Java
  Python3
  # 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#
  PHP
  Output :
  0 2 0
  Recommended Posts:
  - Replace every array element by Bitwise Xor of previous and next element
  - Delete array element in given index range [L - R]
  - Replace every element of the array by its previous element
  - Replace every array element by sum of previous and next
  - Replace every array element by multiplication of previous and next
  - Elements greater than the previous and next element in an Array
  - Find element at given index after given range reversals
  - Rearrange an array such that every odd indexed element is greater than it previous
  - Construct an array from XOR of all elements of array except element at same index
  - Find start and ending index of an element in an unsorted array
  - Find index of an extra element present in one sorted array
  - Previous greater element
  - Array range queries for searching an element
  - Given an array and two integers l and r, find the kth largest element in the range [l, r]
  - Replace the maximum element in the array by coefficient of, sahilshelangia