[LeetCode] 1310. XOR Queries of a Subarray

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [left, right].

For each query i compute the XOR of elements from left to right (that is, arr[left] XOR arr[left + 1] XOR … XOR arr[right] ).

Return an array answer where answer[i] is the answer to the ith query.

Example 1:
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[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

Example 2:
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:
1 <= arr.length, queries.length <= 3 * 104
1 <= arr[i] <= 109
queries[i].length == 2
0 <= lefti <= righti < arr.length

子数组异或查询。

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

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

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

思路

思路是前缀和，而且是一道位运算的前缀和题目。因为题目要我们返回一些 queries 的结果，queries 都是一些区间，所以大概率是前缀和做。同时异或运算（XOR）是怎么处理前缀和的呢？假如 input 数组的前 i 项的 XOR 前缀和为 a, 前 j 项的 XOR 前缀和为 b, 那么 a xor b 就是 input 数组的 [i + 1, j) 项的 XOR 结果。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] presum = new int[n + 1];
        presum[0] = arr[0];
        for (int i = 0; i < n; i++) {
            presum[i + 1] = presum[i] ^ arr[i];
        }

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int[] query = queries[i];
            int left = query[0];
            int right = query[1];
            res[i] = presum[left] ^ presum[right + 1];
        }
        return res;
    }
}