Explanation

Whenever we come across range queries, prefix sums should immediately come to mind. However, since we are dealing with XOR sums over a range, we have to use a prefix XOR array rather than a prefix sum array. To do so, we can define $\texttt{prefix}$ as an array such that $\texttt{prefix}[i]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[i]$. Thus, for each query $(a, b)$, our answer is simply $\texttt{prefix}[a-1]\oplus \texttt{prefix}[b]$.

Proof

We know that $\texttt{prefix}[a-1]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[a-1]$. We also know that $\texttt{prefix}[b]= \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[b]$.

Therefore, since $x\oplus x = 0$ for any $x$:

$\texttt{prefix}[a-1] \oplus \texttt{prefix}[b]= \underbrace{\texttt{arr}[0] \oplus \texttt{arr}[0] \oplus \texttt{arr}[1] \oplus \texttt{arr}[1] \oplus \dots \oplus \texttt{arr}[a-1] \oplus \texttt{arr}[a-1]}_{\text{cancels out to 0}} \oplus \texttt{arr}[a] \oplus \texttt{arr}[a+1] \dots \oplus \texttt{arr}[b]$.

This simplifies to $\texttt{arr}[a] \oplus \texttt{arr}[a+1] \dots \oplus \texttt{arr}[b]$, which is exactly what we're looking for.

Implementation

Time Complexity: $\mathcal{O}(N+Q)$

Copy
n, q = map(int, input().split())
arr = list(map(int, input().split()))

xor_arr = [0] * (n + 1)
for i in range(1, n + 1):
	xor_arr[i] = arr[i - 1] ^ xor_arr[i - 1]

for _ in range(q):
	a, b = map(int, input().split())
	print(xor_arr[b] ^ xor_arr[a - 1])