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
- This is the XOR analogue of prefix sums: define
prefix[i]as the XOR of the firstielements. - Because XOR is its own inverse, the XOR of
arr[left..right]isprefix[right + 1] ^ prefix[left]. - The shared prefix before
leftappears in both terms and cancels, leaving exactly the requested window. - 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]: withprefix[i]defined as the firstielements, the left term isprefix[left]. - Forgetting the off-by-one on the right: the upper term is
prefix[right + 1], because the prefix array has lengthn + 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.