731. The XOR of Every Range
An array is given, then q queries. Each query is l r and asks for the bitwise XOR of
a[l] through a[r] inclusive, with positions numbered from 1.
Print one answer per query.
1 3 4 8, queries (1 2) (1 4) (2 3) (3 3) -> 2 14 7 4
7 7, queries (1 2) (1 1) -> 0 7
## XOR is its own inverse, and that is the whole reason this works
A prefix sum answers a range query by SUBTRACTING, because subtraction undoes addition. XOR needs no separate inverse operation at all:
x ^ x = 0 and x ^ 0 = x
So with P[0] = 0 and P[i] = a[1] ^ a[2] ^ ... ^ a[i],
a[l] ^ ... ^ a[r] = P[r] ^ P[l-1]
because everything from position 1 to l-1 appears in BOTH terms and cancels itself out.
Writing P[r] - P[l-1] is the reflex to resist. Subtraction is meaningless here; the
combining operation and the undoing operation are the same one.
## Why P[0] = 0 is not a convention but a requirement
0 is the identity for XOR, the way 0 is the identity for addition. A query starting at
position 1 uses P[0], and it must contribute nothing. Seeding it with anything else corrupts
every such query and leaves the rest correct, which is the most awkward kind of bug to find.
## Problem 61 is the same shape
61 builds a prefix SUM array and answers with one subtraction. This builds a prefix XOR array and answers with one XOR. The pattern works for any operation with an identity and an inverse, which is worth noticing because addition and XOR are the two that come up.
## Overflow
XOR can produce a value larger than either operand, 1 ^ 2 = 3 being the smallest example, so
the guarantee is about bit WIDTH and not about magnitude: XOR never sets a bit that none of its
operands had, so the result stays inside the widest input.
Here the values reach 10^9, and 10^9 < 2^30 = 1073741824, so every input uses at most 30
bits and every prefix XOR stays below 2^30 as well. Nothing can overflow a signed 32 bit
integer, and in particular the sign bit is never set. That is unusual enough to be worth
saying: in a prefix SUM the running total grows without bound, while a prefix XOR stays inside
the width of the inputs forever.
The familiar C and C++ advice to hold XOR results in an unsigned type only starts to matter if
the value bound is raised past 2^31, where the sign bit can actually be set. Under these
constraints it cannot be, so either type works.
## Cost
Time O(n + q). Space O(n).
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ each value ≤ 10^9` - `1 ≤ l ≤ r ≤ n`
Input
The first line contains two integers n and q.
The second line contains n integers.
Each of the next q lines contains two integers l and r.
Output
Print q lines, one XOR per query.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.