XOR Queries of a Subarray: Prefix XOR Pattern

LeetCode XOR Queries of a Subarray (Problem 1310) gives you an array arr and a list of queries. Each query is a pair [left, right], and you need to return the XOR of all elements from arr[left] to arr[right] inclusive.

A brute force approach would loop through the subarray for each query. But with up to 30,000 queries on an array of up to 30,000 elements, that gets slow fast. The trick is to precompute a prefix XOR array so every query takes O(1).

Why this problem matters

This is the XOR version of prefix sums. If you have seen prefix sums before, you already know the template. The only difference is that you swap addition for XOR and subtraction for... also XOR. That is the beautiful thing about XOR: the same operation that builds the prefix also undoes it. The self-cancellation property (a XOR a = 0) plays the exact role that subtraction plays for prefix sums.

Once you internalize prefix XOR, you can apply the same idea to any associative, invertible operation. It shows up in competitive programming, interview problems, and systems code dealing with checksums and error detection.

The key insight

Build a prefix XOR array where prefix[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1], with prefix[0] = 0. Then the XOR of any subarray [left, right] is simply prefix[right + 1] XOR prefix[left].

Why does this work? When you XOR prefix[right + 1] with prefix[left], all the terms from arr[0] through arr[left - 1] appear in both prefix values. XOR is self-inverse, so those shared terms cancel to zero. What remains is exactly arr[left] XOR arr[left + 1] XOR ... XOR arr[right].

The solution

def xor_queries(arr: list[int], queries: list[list[int]]) -> list[int]:
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i + 1] = prefix[i] ^ arr[i]

    result = []
    for left, right in queries:
        result.append(prefix[right + 1] ^ prefix[left])
    return result

The function builds the prefix array in one pass, then answers each query with a single XOR operation. No nested loops, no repeated work.

Visual walkthrough

Notice that building the prefix array is the only real work. Once you have it, every query is a constant-time lookup and XOR. The prefix array is the precomputation that turns repeated O(n) work into O(1) answers.

Complexity analysis

Here n is the length of arr and q is the number of queries. Building the prefix array takes O(n). Each query takes O(1), and there are q of them. The prefix array uses O(n) extra space.

A brute force approach that iterates through the subarray for every query would be O(n * q) in the worst case. The prefix XOR approach eliminates that redundant work entirely.

The building blocks

1. Prefix XOR construction

prefix = [0] * (len(arr) + 1)
for i in range(len(arr)):
    prefix[i + 1] = prefix[i] ^ arr[i]

This is the same loop structure as prefix sums, just with ^ instead of +. The extra element at index 0 (set to 0) simplifies the range query formula. Without it, you would need a special case when left == 0.

2. Range XOR query

def range_xor(prefix, left, right):
    return prefix[right + 1] ^ prefix[left]

One XOR, two lookups. The prefix values at right + 1 and left encode everything you need. The terms before left cancel out, and the terms from left through right remain.

Edge cases

• Single element query. When left == right, you get prefix[left + 1] ^ prefix[left], which simplifies to arr[left]. The formula handles it naturally.
• Full array query. When left = 0 and right = len(arr) - 1, you get prefix[len(arr)] ^ prefix[0], which is the XOR of the entire array. The prefix[0] = 0 initialization makes this clean.
• All elements are zero. Every prefix value is 0, and every query returns 0. No special handling needed.
• All elements are the same. If every element is x, then XOR-ing an even number of them gives 0 and an odd number gives x. The prefix array captures this pattern correctly.

From understanding to recall

You have seen the prefix XOR pattern and traced through the examples. But the next time a problem asks you to compute XOR over subarrays, will the solution come to you immediately? That is the gap between understanding and recall.

The fix is spaced repetition. You practice building the prefix array and writing the range query formula from scratch, at increasing intervals, until the pattern is automatic. After a few reps, you stop thinking about XOR tables and cancellation proofs. You just see "range XOR" and your hands write the prefix loop.

Related posts

• Single Number - XOR cancellation pattern to find the unique element
• Product of Array Except Self - Another prefix computation technique
• Subarray Sum Equals K - Prefix sums for range queries

Prefix XOR is one of those patterns that pays dividends far beyond a single problem. Master it once, and you will recognize it everywhere: checksums, parity checks, range queries, and more.