⚡Flashcard Drill➔
NeetCode #867LC-1310MediumBit Manipulation
← Back to All Problems

#867 · #1310 · XOR Queries of a Subarray(子数组异或查询)

📌 Problem Statement & Constraints

Given an array arr and an array of queries where queries[i] = [left, right], return an array holding the XOR of arr[left..right] for each query. Constraints: 1 <= arr.length, queries.length <= 3 * 10^4, 0 <= arr[i] <= 10^9, 0 <= left <= right < arr.length.

💡 Core Algorithmic Approaches

  1. This is the XOR analogue of prefix sums: define prefix[i] as the XOR of the first i elements.
  2. Because XOR is its own inverse, the XOR of arr[left..right] is prefix[right + 1] ^ prefix[left].
  3. The shared prefix before left appears in both terms and cancels, leaving exactly the requested window.
  4. Precompute the prefix array once, then answer each query in O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i, x in enumerate(arr):
            prefix[i + 1] = prefix[i] ^ x
        res = []
        for left, right in queries:
            res.append(prefix[right + 1] ^ prefix[left])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + q): one preprocessing pass and one step per query.
💾 Space Complexity
O(n): the prefix array (plus the output).

⚠️ Interview Pitfalls & Follow-ups

  • Scanning each query's range: O(n * q) with up to 3 * 10^4 of each, which times out.
  • Using prefix[left - 1]: with prefix[i] defined as the first i elements, the left term is prefix[left].
  • Forgetting the off-by-one on the right: the upper term is prefix[right + 1], because the prefix array has length n + 1.
  • Trying to subtract XOR values: XOR has no subtraction; the cancellation comes from XOR-ing the same value twice.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Bit Manipulation Problems