Editorial for Range XOR

Approach

Let $pref_i$ be the XOR of the first $i$ elements:

• $pref_0 = 0$
• $pref_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$

XOR is its own inverse, so:

$pref_r \oplus pref_{l - 1} = (a_1 \oplus \cdots \oplus a_{l - 1} \oplus a_l \oplus \cdots \oplus a_r) \oplus (a_1 \oplus \cdots \oplus a_{l - 1}) = a_l \oplus \cdots \oplus a_r$

So we first build the prefix XOR array in $O(n)$, then answer each query in $O(1)$.

The total time complexity is $O(n + q)$.

Solution (Python)

import sys


n = int(input())
values = list(map(int, input().split()))

prefix = [0] * (n + 1)
for i, value in enumerate(values, start=1):
    prefix[i] = prefix[i - 1] ^ value

q = int(input())
answers = []
for _ in range(q):
    l, r = map(int, input().split())
    answers.append(str(prefix[r] ^ prefix[l - 1]))

sys.stdout.write("\n".join(answers) + "\n")