Domain 2MediumMEDIUM

XOR Queries of a Subarray

LeetCode problem 1310: XOR Queries of a Subarray (medium).

Domain: medium•Updated: 2026-09-14
#Bit Manipulation

Problem Breakdown

We are given an array arr and a list of queries. Each query specifies a range [L, R]. For every query, we must calculate the bitwise XOR sum of all elements within that inclusive range (from index L to index R).

Inputs:

  • An integer array arr.
  • A 2D integer array queries where each row is [Li, Ri].

Outputs:

  • A list containing the computed XOR result for every query in order.

Constraints & Edge Cases:

  • Array length and number of queries are up to 3×1043 \times 10^4. This suggests an O(N)O(N) or O(Q)O(Q) solution is required; anything quadratic will likely TLE (Time Limit Exceeded).
  • Values fit within standard integer types. Python handles large integers automatically, so overflow isn’t a concern here compared to languages like C++/Java where XORing 32-bit ints might need specific handling if values exceeded 231−12^{31}-1, though the logic remains identical.
  • Indices are guaranteed valid (0≤L≤R<arr.length0 \le L \le R < arr.length), so we don’t strictly need bounds checking for indices, but robust code handles empty arrays gracefully anyway (though constraints say length ≥1\ge 1).

Intuition

If we naively iterate from L to R for every query, the complexity per query is O(N)O(N). With QQ queries, total time becomes O(Q×N)O(Q \times N), which is roughly (3⋅104)2=9⋅108(3 \cdot 10^4)^2 = 9 \cdot 10^8 operations. This exceeds typical limits (usually ∼107−108\sim 10^7-10^8 ops/sec).

Key Insight: XOR behaves similarly to addition regarding prefix sums, but with a crucial property: x⊕x=0x \oplus x = 0. If we define prefix[i] as the XOR sum of all elements from index 0 to i-1, then the XOR sum for range [L, R] can be derived by canceling out the prefix before L. Mathematically: (arr[0] ^ ... ^ arr[R]) ^ (arr[0] ^ ... ^ arr[L-1]) = arr[L] ^ ... ^ arr[R]. This reduces each query to an O(1)O(1) lookup after preprocessing.

Approach

  1. Preprocessing: Construct a prefix_xor array of size len(arr) + 1. Initialize the first element as 0 (identity for XOR). Iterate through arr, updating the cumulative XOR at index i+1 using value from index i.
  2. Query Processing: For each query [L, R]:
    • Retrieve the prefix sum up to R + 1 (prefix_xor[R+1]).
    • Retrieve the prefix sum up to L (prefix_xor[L]).
    • Compute result as their XOR: res = prefix_xor[R+1] ^ prefix_xor[L].
  3. Result Construction: Append each computed result to a list and return it.

Complexity Analysis

  • Time Complexity: O(N+Q)O(N + Q). We iterate through the array once (NN operations) to build the prefix table, then perform constant-time work for each of the QQ queries. Given constraints, this is highly efficient.
  • Space Complexity: O(N)O(N) to store the prefix_xor auxiliary array.

Solution

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        
        # Step 1: Build prefix XOR array of size N + 1
        # prefix_xor[i] stores the XOR sum of arr[0...i-1]
        prefix_xor = [0] * (n + 1)
        
        current_xor = 0
        for i in range(n):
            current_xor ^= arr[i]
            prefix_xor[i + 1] = current_xor
            
        # Step 2: Answer queries using the property that 
        # XOR(L...R) = Prefix(R+1) ^ Prefix(L)
        result = []
        
        for L, R in queries:
            res = prefix_xor[R + 1] ^ prefix_xor[L]
            result.append(res)
            
        return result

Edge Cases Handled

  • Single Element Range: When L == R, the logic correctly computes prefix_xor[R+1] ^ prefix_xor[R]. Since prefix_xor[R+1] = prefix_xor[R] ^ arr[R], XORing them cancels out everything before R and leaves exactly arr[R].
  • Full Array Query: When [0, n-1], it computes prefix_xor[n] ^ prefix_xor[0]. Since prefix_xor[0] = 0, this returns the total XOR of the array.
  • Large Values: Python integers handle arbitrary size automatically; bitwise operations work correctly regardless of bit-width (unlike fixed-size integer languages).