Prerequisites: Binary Indexed Tree.
Problem
Given an array A of size n and an array Q of size q containing the following two types of queries:
 (1, L, R): Return the XOR of all elements present between the array indices L and R.
 (2, i, value): Update the value of A[i] to (A[i] XOR value).
Solve each Query using Fenwick Tree and print the result of every Query of 1st type.
Input:
 An integer n.
 The next n lines contain the array elements.
 The next line contains an integer q that represents the size of the Q array.
 The next q lines contain queries to resolve.
Output: Print the result of every Query of 1st type in a new line.
Questions you can ask the interviewer:
 What are the constraints on n and q?
 What is the range of the elements of A?
Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing time and spaceefficient code and compete in code competitions worldwide.
Example,
Input: n = 9, A = {1, 2, 3, 4, 5, 6, 7, 8, 9}, q = 3, Q = {{ 1, 2, 5}, {2, 4, 2}, {1, 2, 5}}. Output: XOR of the elements between 2 to 5 is 4. XOR of the elements between 2 to 5 is 6. Explanation:

Recommended: Try to solve it yourself before moving on to the solution.
Solution
Idea: The idea is to solve it using Fenwick Tree. Build Binary Index Tree of the array elements.
Define a getXOR(x) function that will return the XOR of array elements with index range [1, x].
For queries of Type1: For XOR of range [ l, r], return the Xor of elements in range [1, R] and range[1, L1] i.e. ( getXOR(r) XOR getXOR(l1) ).
For queries of Type2: Define an updateBITree function that will update the values in Binary Index Tree according to the queries.
Algorithm:
 In getXOR(), keep computing XOR using BinTree[i] for starting index i to all its ancestors until 1. In the getXOR(), subtract LSB(least Significant Bit) from i as i = i – i&(i) to get the ancestor of the ith index. Return the XOR computed.
 In updateBITree(), update A[i] to A[i] ^ value. Update all ranges that include this index in BITree using the updateBIT() function.
 In updateBITree(), to get ancestor of ith index, add LSB(least Significant Bit) to i: i = i + i&(i).
C++
#include <bits/stdc++.h> //update XOR.

Input: n = 9, A = {1, 2, 3, 4, 5, 6, 7, 8, 9}, q = 3, Q = {{ 1, 2, 5}, {2, 4, 2}, {1, 2, 5}}.
Output:
Time complexity: O(q * logn)
Time complexity of getXOR(): O(logn).
Time complexity of updateBITree(): O(long).
Also read, Euclid GCD Algorithm