Pattern visualizer
XOR Queries of a Subarray
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. 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..
Prefix XOR turns every range query into one operation
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.
1FUNCTION xorQueries(arr, queries):2 prefix[0] <- 03 FOR i <- 1 TO LENGTH(arr):4 prefix[i] <- prefix[i - 1] XOR arr[i - 1]5 out <- empty list6 FOR EACH (l, r) IN queries:7 answer <- prefix[r + 1] XOR prefix[l]8 APPEND answer TO out9 RETURN out
← / → step · space play · Home restart