前缀和题目：子数组异或查询

题目

标题和出处

标题：子数组异或查询

出处：1310. 子数组异或查询

难度

4 级

题目描述

要求

给定一个正整数数组 $\text{arr}$，以及一个查询数组 $\text{queries}$，其中 ${\text{queries[i] = [left}}_{\text{i}}{\text{, right}}_{\text{i}}\text{]}$。

对于每个查询 $\text{i}$，计算从 ${\text{left}}_{\text{i}}$ 到 ${\text{right}}_{\text{i}}$ 的异或值（即 ${\text{arr[left}}_{\text{i}}\text{]}\oplus {\text{arr[left}}_{\text{i}}\text{ + 1]}\oplus \dots \oplus {\text{arr[right}}_{\text{i}}\text{]}$）作为查询的结果。

返回一个数组 $\text{answer}$，其中 $\text{answer[i]}$ 是第 $\text{i}$ 个查询的结果。

示例

示例 1：

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

示例 2：

输入：$\text{arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]}$
输出：$\text{[8,0,4,4]}$

数据范围

• $\text{1}\le \text{arr.length}\le \text{3}\times {\text{10}}^{\text{4}}$
• $\text{1}\le \text{arr[i]}\le {\text{10}}^{\text{9}}$
• $\text{1}\le \text{queries.length}\le \text{3}\times {\text{10}}^{\text{4}}$
• $\text{queries[i].length}=\text{2}$
• $\text{0}\le {\text{left}}_{\text{i}}\le {\text{right}}_{\text{i}}<\text{arr.length}$

解法

思路和算法

这道题要求对于每个查询计算子数组的元素按位异或。由于数组 $\text{arr}$ 的长度以及查询的个数最大为 $3\times 10^4$，因此计算子数组的元素按位异或时，不能使用遍历子数组的做法，而是需要使用时间复杂度更低的做法。可以使用前缀和的思想实现。

首先计算数组 $\text{arr}$ 的前缀异或数组。创建前缀异或数组 $\text{prefixXors}$，其长度为 $\text{arr}$ 的长度加 $1$，$\text{prefixXors}[i]$ 表示 $\text{arr}$ 的长度为 $i$ 的前缀异或，即下标范围 $[0,i-1]$ 中的 $i$ 个元素的按位异或。

根据按位异或的性质，$\text{prefixXors}[i+1]\oplus \text{prefixXors}[i]=\text{arr}[i]$，$\text{prefixXors}[i+1]=\text{prefixXors}[i]\oplus \text{arr}[i]$，由此可以遍历数组 $\text{arr}$ 一次计算得到前缀异或数组。

得到前缀异或数组 $\text{prefixXors}$ 之后，对于 $\text{queries}[i]=[{\text{left}}_i,{\text{right}}_i]$，查询结果可以通过前缀异或数组得到：

$$\text{answer}[i]=\text{prefixXors}[{\text{right}}_i+1]\oplus \text{prefixXors}[{\text{left}}_i]$$

代码

class Solution {public int[] xorQueries(int[] arr, int[][] queries) {int length = arr.length;int[] prefixXors = new int[length + 1];for (int i = 0; i < length; i++) {prefixXors[i + 1] = prefixXors[i] ^ arr[i];}int queriesCount = queries.length;int[] answer = new int[queriesCount];for (int i = 0; i < queriesCount; i++) {int left = queries[i][0], right = queries[i][1];answer[i] = prefixXors[right + 1] ^ prefixXors[left];}return answer;}
}

复杂度分析

• 时间复杂度：$O(n+q)$，其中 $n$ 是数组 $\text{arr}$ 的长度，$q$ 是数组 $\text{queries}$ 的长度。需要遍历数组 $\text{arr}$ 一次计算前缀异或数组，需要遍历数组 $\text{queries}$ 一次计算每个查询的结果，每个查询的计算时间是 $O(1)$，因此时间复杂度是 $O(n+q)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{arr}$ 的长度。需要创建长度为 $n+1$ 的前缀异或数组。