1310. XOR Queries of a Subarray
LeetCode 1310. XOR Queries of a Subarray
Description
Given the array arr
of positive integers and the array queries
where queries[i] = [Li, Ri]
, for each query i
compute the XOR of elements from Li
to Ri
(that is, arr[Li] **xor** arr[Li+1] **xor** ... **xor** arr[Ri]
). Return an array containing the result for the given queries
.
Example 1:
Example 2:
Constraints:
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
Tags
Bit Manipulation
Solution
A skilled application of the "prefix sum" technique can help us solve "range sum" problems with lower time complexity.
We first build a prefix sum array prefix
where prefix[i] = arr[:i+1]
. Then, we initialize a result array ans
with the length of queries
, and, based on the knowledge that , we can obtain the result of a query [l, r]
is prefix[l-1] ^ prefix[r]
. If l == 0
, the result is just prefix[r]
. At last, we return ans
.
Complexity
Time complexity:
Space complexity:
Code
Last updated
Was this helpful?