What is the most efficient way to solve XOR Queries of a Subarray?

Use a prefix XOR array so each query is answered in constant time by computing prefix[right+1] ^ prefix[left].

Why use prefix XOR instead of iterating each subarray?

Iterating each subarray results in O(n*q) complexity which is too slow; prefix XOR reduces each query to O(1).

How does XOR property x ^ x = 0 help in this problem?

It allows the cancellation of overlapping elements in prefix XOR, enabling fast subarray computation without recomputation.

Can this approach handle large arrays and many queries?

Yes, because building the prefix array is O(n) and each query is O(1), making it scalable for arrays up to 3*10^4 elements.

Is there a variant for 2D arrays?

Yes, prefix XOR can be extended to 2D matrices, computing submatrix XOR using similar cancellation principles.

#1310

Medium

auto_awesome前缀和

LeetCode 题解工作台

子数组异或查询

有一个正整数数组 arr ，现给你一个对应的查询数组 queries ，其中 queries[i] = [L i, R i ] 。对于每个查询 i ，请你计算从 L i 到 R i 的 XOR 值（即 arr[L i ] xor arr[L i +1] xor ... xor arr[R i ] …

数组位运算前缀和

题目描述

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [L_i,R_i]。

对于每个查询 i，请你计算从 L_i 到 R_i 的 XOR 值（即 arr[L_i] xor arr[L_i+1] xor ... xor arr[R_i]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 1：

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8] 
解释：
数组中元素的二进制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

示例 2：

输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]

提示：

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

lightbulb

解题思路

方法一：前缀异或

我们可以用一个长度为 $n+1$ 的前缀异或数组 $s$ 来存储数组 $\textit{arr}$ 的前缀异或结果，其中 $s[i] = s[i-1] \oplus \textit{arr}[i-1]$ ，即 $s[i]$ 表示 $\textit{arr}$ 的前 $i$ 个元素的异或结果。

那么对于一个查询 $[l,r]$ ，我们可以得到：

\begin{aligned} \textit{arr}[l] \oplus \textit{arr}[l+1] \oplus \cdots \oplus \textit{arr}[r] &= (\textit{arr}[0] \oplus \textit{arr}[1] \oplus \cdots \oplus \textit{arr}[l-1]) \oplus (\textit{arr}[0] \oplus \textit{arr}[1] \oplus \cdots \oplus \textit{arr}[r]) \\ &= s[l] \oplus s[r+1] \end{aligned}

时间复杂度 $O(n+m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{arr}$ 的长度和查询数组 $\textit{queries}$ 的长度。

1

2

3

4

5

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        s = list(accumulate(arr, xor, initial=0))
        return [s[r + 1] ^ s[l] for l, r in queries]

speed

复杂度分析

指标	值
时间	complexity is O(n + q), where n is array length and q is number of queries, because building the prefix array takes O(n) and each query is answered in O(1). Space complexity is O(n) for the prefix XOR array, but additional space for output is negligible.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Check if you recognize that XOR has an inverse property that allows prefix computations.
question_mark
They might ask for an optimization beyond naive O(n*q) subarray calculation.
question_mark
Expect a hint about building cumulative data structures, specifically prefix XOR, for constant-time queries.

warning

常见陷阱

外企场景

error
Not initializing prefix array with zero leading to incorrect XOR for subarrays starting at index 0.
error
Attempting to iterate over the subarray for each query, resulting in TLE for large inputs.
error
Misunderstanding XOR properties, especially forgetting that x ^ x = 0 can simplify calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute XOR for dynamic ranges where elements are updated between queries.
arrow_right_alt
Use XOR queries on a 2D matrix instead of a 1D array, applying similar prefix ideas.
arrow_right_alt
Determine the maximum XOR among all subarray ranges instead of specific queries.

help

常见问题

外企场景

继续练习

#1442 形成两个异或相等数组的三元组数目 #1177 构建回文串检测 #995 K 连续位的最小翻转次数