CSES - Range Xor Queries

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
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 2e5;

int n, q, arr[MAX_N + 1], prefix[MAX_N + 1], a, b;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

Copy
import java.io.*;
import java.util.*;

public class RangeXorQueries {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int q = io.nextInt();

		// arr and prefix use 1-based indexing

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])