XOR Queries of a Subarray

Prefix XOR turns every range query into one operation

time O(n + q)space O(n)

XOR is its own inverse: x XOR x = 0, so anything XORed in twice disappears. That makes it behave like a prefix sum. Build prefix[i] = the XOR of everything before index i, and any range [l,r] is prefix[r+1] XOR prefix[l] — the shared head arr[0..l-1] appears in both, cancels itself, and what survives is exactly the range you asked for. The extra leading 0 keeps queries that start at index 0 on the same formula as the rest.

Details

Animated on: arr = [1,3,4,8,2,6], queries = [[0,1],[1,3],[0,5],[4,4],[2,5]] — return the XOR of each requested range.

Problem:XOR Queries of a SubarrayMedium

Prefix XOR turns every range query into one operation

step 1 / 14

[0]

[1]

[2]

[3]

[4]

[5]

arr = [1,3,4,8,2,6] with 5 queries to answer. XORing each range on its own re-reads the same cells over and over; instead notice that XOR undoes itself, so one pass can prepare every answer.

Pseudocode

1FUNCTION xorQueries(arr, queries):
2  prefix[0] <- 0
3  FOR i <- 1 TO LENGTH(arr):
4    prefix[i] <- prefix[i - 1] XOR arr[i - 1]
5  out <- empty list
6  FOR EACH (l, r) IN queries:
7    answer <- prefix[r + 1] XOR prefix[l]
8    APPEND answer TO out
9  RETURN out

← / → step · space play · Home restart

Every step in words

Show all 14 steps

arr = [1,3,4,8,2,6] with 5 queries to answer. XORing each range on its own re-reads the same cells over and over; instead notice that XOR undoes itself, so one pass can prepare every answer.
prefix[0] = 0 because it XORs no elements at all, and 0 is XOR's do-nothing value — this empty slot is what lets a query that starts at index 0 use the same formula as every other query.
prefix[1] = prefix[0] XOR arr[0] = 0 XOR 1 = 1, so this cell now carries the XOR of arr[0..0] = [1] in a single number.
prefix[2] = prefix[1] XOR arr[1] = 1 XOR 3 = 2, so this cell now carries the XOR of arr[0..1] = [1,3] in a single number.
prefix[3] = prefix[2] XOR arr[2] = 2 XOR 4 = 6, so this cell now carries the XOR of arr[0..2] = [1,3,4] in a single number.
prefix[4] = prefix[3] XOR arr[3] = 6 XOR 8 = 14, so this cell now carries the XOR of arr[0..3] = [1,3,4,8] in a single number.
prefix[5] = prefix[4] XOR arr[4] = 14 XOR 2 = 12, so this cell now carries the XOR of arr[0..4] = [1,3,4,8,2] in a single number.
prefix[6] = prefix[5] XOR arr[5] = 12 XOR 6 = 10, so this cell now carries the XOR of arr[0..5] = [1,3,4,8,2,6] in a single number.
Query [0,1]: prefix[2] = 2 covers arr[0..1] and prefix[0] = 0 covers nothing. XORing the two cancels that shared head, leaving 2 XOR 0 = 2 — the XOR of [1,3], read in one operation instead of 2.
Query [1,3]: prefix[4] = 14 covers arr[0..3] and prefix[1] = 1 covers arr[0..0]. XORing the two cancels that shared head, leaving 14 XOR 1 = 15 — the XOR of [3,4,8], read in one operation instead of 3.
Query [0,5]: prefix[6] = 10 covers arr[0..5] and prefix[0] = 0 covers nothing. XORing the two cancels that shared head, leaving 10 XOR 0 = 10 — the XOR of [1,3,4,8,2,6], read in one operation instead of 6.
Query [4,4]: prefix[5] = 12 covers arr[0..4] and prefix[4] = 14 covers arr[0..3]. XORing the two cancels that shared head, leaving 12 XOR 14 = 2 — the XOR of [2], and even this single cell is read without touching arr at all.
Query [2,5]: prefix[6] = 10 covers arr[0..5] and prefix[2] = 2 covers arr[0..1]. XORing the two cancels that shared head, leaving 10 XOR 2 = 8 — the XOR of [4,8,2,6], read in one operation instead of 4.
All 5 queries answered as [2,15,10,2,8] after one 6-element pass, because every range answer was already sitting in the prefix table as the difference between two of its cells.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve XOR Queries of a Subarray in the editor All Bit Manipulation problems Back to roadmap