What is the brute force approach and complexity for XOR Queries of a Subarray?

For each query, XOR arr[left..right] from scratch with time complexity O(N · Q) and space complexity O(1).

What is the optimal approach and complexity for XOR Queries of a Subarray?

Build prefix XORs once; each query is prefix[r+1] ^ prefix[l] with optimal time complexity O(N + Q) and space complexity O(N).

How do you identify the pattern for XOR Queries of a Subarray?

Look for key signals in the prompt: "XOR of arr[left] … arr[right]" indicates A range of one array. Like a range sum, it is built from two prefix totals.; "many queries, the array never changes" indicates Compute the prefix XORs once. After that each query is O(1).; "XOR, not addition" indicates XOR is its own inverse, so the subtraction step of prefix sums becomes another XOR..

XOR Queries of a Subarray

Medium·LeetCode #1310Basic Anchor

LeetCode

Jump:

30-Second Mental ModelRange bitwise properties — prefix XOR (static range query)

Complexity:O(N · Q)→O(N + Q)

Key Insight

Build prefix, where prefix[i] is the XOR of everything before index i, with prefix[0] = 0. Then the XOR of arr[l..r] is prefix[r + 1] ^ prefix[l]. The part before l is in both prefixes, and XOR-ing it twice cancels it out. Each query is then a single XOR.

Core Validity Invariant

prefix[i] always means the XOR of everything strictly before index i. Then arr[l..r] is prefix[r + 1] ^ prefix[l], because the part before l appears in both and cancels.

Problem

You get an array arr of positive integers and a list of queries. Each query is a pair [left, right]. The answer to a query is the XOR of the numbers from arr[left] to arr[right], both ends included: arr[left] ^ arr[left + 1] ^ … ^ arr[right].

Return one answer for each query, in the same order as the queries.

Input

An array arr of positive integers, and a list queries of [left, right] pairs.

Output

An array with one answer per query, in the same order.

Example 1

Input: arr = [1, 3, 4, 8], queries = [[0, 1], [1, 2], [0, 3], [3, 3]]

Output: [2, 7, 14, 8]

1 ^ 3 = 2 (0001 ^ 0011 = 0010). 3 ^ 4 = 7. 1 ^ 3 ^ 4 ^ 8 = 14. A range of one number is that number, so the last answer is 8.

Example 2

Input: arr = [4, 8, 2, 10], queries = [[2, 3], [1, 3], [0, 0], [0, 3]]

Output: [8, 0, 4, 4]

2 ^ 10 = 8. 8 ^ 2 ^ 10 = 0. A single 4 is 4. 4 ^ 8 ^ 2 ^ 10 = 4.

Constraints

• 1 ≤ arr.length ≤ 3 · 10^4 and 1 ≤ queries.length ≤ 3 · 10^4
• 1 ≤ arr[i] ≤ 10^9
• queries[i] has exactly 2 numbers: [left, right]
• 0 ≤ left ≤ right < arr.length

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Range Sum Query asked for sums. What should replace the adding here, and what happens when a value is XOR-ed with itself?
2.
If three queries all cover index 1, how many times does the brute force XOR arr[1] in total?
3.
Can I store one value per position that says "everything up to here"? How many of those values would I need?
4.
If I know the XOR of everything up to r and the XOR of everything before l, how do I get the middle part?
5.
Is XOR's inverse the same operation as subtraction? What does x ^ x equal?

Brute force approach

Idea

For each query, start at 0 and XOR in every element from left to right. Then move on to the next query and start again.

Thinking process

1
The question asks for the XOR of a range. The direct way is a loop that XORs each element of the range into one number.
2
Check it by hand on query [1, 2] of [1, 3, 4, 8]: 3 ^ 4 = 0011 ^ 0100 = 0111 = 7. Two XORs, and the answer is right.
3
The cost is the length of each range. A query that covers the whole array needs N XORs.
4
The waste: queries overlap. [0, 1] and [0, 3] both XOR arr[0] and arr[1] from scratch, and nothing is saved between them.

Visual

Orange cells were already XOR-ed for an earlier query. The bits are 4-bit values, most significant bit on the left.

Brute force repeats the same XORsarr = [1, 3, 4, 8], queries = [[0, 1], [1, 2], [0, 3], [3, 3]]step 1/13

arr

▲i

Work

[left, right]: [0, 1]
already XOR-ed for an earlier query: no
XOR steps so far: 1

XOR arr[0] = 1 into x

x = 0 ^ 1 = 1.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        vector<int> answer;
        for (auto& q : queries) {
            int x = 0;
            // XOR every element of this query's range from scratch.
            for (int i = q[0]; i <= q[1]; i++) {
                x ^= arr[i];
            }
            answer.push_back(x);
        }
        return answer;
    }
};

Complexity

Time O(N · Q)Space O(1)

N = arr.length and Q = queries.length. A query costs as many XORs as its range has elements, so the worst case is about N · Q = 9 · 10^8 XORs when every query covers the whole array. The extra space is O(1), apart from the answer list every approach returns.

Optimized approach

Idea

Start from brute force

The brute force XORs each range from scratch, for every query.

Find the repeated work

Overlapping queries XOR the same elements again and again. [0, 1] and [0, 3] both XOR arr[0] and arr[1]. The array never changes, so the XOR of any fixed prefix is the same every time it is needed.

Define the state — what variables do I need?

prefix: Array of size n + 1. prefix[i] = arr[0] ^ … ^ arr[i − 1], the XOR of everything before index i.
prefix[0] = 0: The XOR of nothing. It lets a query that starts at index 0 use the same formula as all the others.
prefix[n]: The XOR of the whole array.

Define validity

prefix[i] always means the XOR of everything strictly before index i. Then arr[l..r] is prefix[r + 1] ^ prefix[l], because the part before l appears in both and cancels.

Define the transitions — when does each pointer move, and why is it safe?

Build, for i = 0 … n − 1

prefix[i + 1] = prefix[i] ^ arr[i]

The XOR of everything before i + 1 is the XOR before i with arr[i] added in. XOR adds one more term in the same way as the running sum in Range Sum Query.

Each query (left, right)

return prefix[right + 1] ^ prefix[left]

prefix[right + 1] XORs arr[0..right]. prefix[left] XORs arr[0..left−1]. Both contain arr[0..left−1], and x ^ x = 0, so that part cancels and leaves arr[left..right].

What does the current window add to the answer?

Each query reads two stored values and XORs them. The work of walking the array was done once, in the build loop.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
        int n = arr.size();

        // prefix[i] = arr[0] ^ ... ^ arr[i-1]. prefix[0] = 0 is the XOR of nothing.
        vector<int> prefix(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] ^ arr[i];
        }

        vector<int> answer;
        for (auto& q : queries) {
            int l = q[0], r = q[1];
            // Both prefixes contain arr[0..l-1]. XOR-ing them cancels that part.
            answer.push_back(prefix[r + 1] ^ prefix[l]);
        }
        return answer;
    }
};

Complexity

Time O(N + Q)Space O(N)

Building prefix takes N steps, and each query is one XOR of two stored values, so Q steps. The brute force takes N · Q. Each query must at least read its own answer, so O(Q) is the floor, and building the prefix costs O(N) once.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	For each query, XOR arr[left..right] from scratch	O(N · Q)	O(1)
Optimal	Build prefix XORs once; each query is prefix[r+1] ^ prefix[l]	O(N + Q)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“XOR of arr[left] … arr[right]”A range of one array. Like a range sum, it is built from two prefix totals.
“many queries, the array never changes”Compute the prefix XORs once. After that each query is O(1).
“XOR, not addition”XOR is its own inverse, so the subtraction step of prefix sums becomes another XOR.

Static array+many range queries+XOR of a range = prefix[r+1] ^ prefix[l]→Range bitwise properties — prefix XOR (static range query)

Range Sum Query - Immutable has the same shape with +: a range is the difference of two prefixes. Here XOR is its own inverse, so the "subtract" step becomes another XOR: x ^ x = 0 removes the shared part. Unlike the next question, this one has an array and many queries, so it needs a prefix array. The next question has no array at all; it asks about a range of consecutive numbers.

Don't make this mistake

Subtracting prefixes, like Range Sum Query

✗ return prefix[right + 1] - prefix[left];

✓ return prefix[right + 1] ^ prefix[left];

This is the pattern-confusion trap. The code looks the same as Range Sum Query, so the - slips in. XOR is not subtraction. On [1, 3, 4, 8], query [1, 2]: prefix[3] − prefix[1] = 6 − 1 = 5, but the answer is 3 ^ 4 = 7. The XOR version gives 6 ^ 1 = 0110 ^ 0001 = 0111 = 7.

Off by one with the 0-based prefix

✗ return prefix[r] ^ prefix[l];

✓ return prefix[r + 1] ^ prefix[l];

prefix[i] stops before index i, so prefix[r] leaves out arr[r]. On [1, 3, 4, 8], query [0, 1]: prefix[1] ^ prefix[0] = 1 ^ 0 = 1, which is just arr[0]. The answer is 1 ^ 3 = 2, and prefix[r + 1] = prefix[2] = 2 gives it.

Prefix array one slot too short

✗ vector<int> prefix(n, 0); // n slots: indices 0 … n-1 for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i]; // writes prefix[n]

✓ vector<int> prefix(n + 1, 0); // n + 1 slots: indices 0 … n

prefix[n] is the XOR of the whole array and needs its own slot. Writing to prefix[n] on a vector of size n is undefined behaviour: it may crash, or silently overwrite memory next to the vector. The leading 0 is what makes the size n + 1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture