Editorial for Range XOR

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

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

$pref_0 = 0$ ~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)$ ~O(n)~, then answer each query in $O(1)$ ~O(1)~.

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

Solution (Python)

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())
for _ in range(q):
    l, r = map(int, input().split())
    print(prefix[r] ^ prefix[l - 1])

Comments

There are no comments at the moment.