一文详解如何思考「区间求和」问题｜Java 刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

题目描述

这是 LeetCode 上的 1310. 子数组异或查询 ，难度为 中等。

Tag : 「数学」、「树状数组」、「前缀和」

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

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

并返回一个包含给定查询 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

基本分析

令数组 arr 和数组 queries 的长度分别为 n 和 m。

n 和 m 的数据范围均为 $10^4$，因此 $O(m * n)$ 的暴力做法我们不用考虑了。

数据范围要求我们做到「对数复杂度」或「线性复杂度」。

本题主要利用异或运算中的「相同数值进行运算结果为 $0$」的特性。

对于特定数组 $[a1, a2, a3, … , an]$，要求得任意区间 $[l, r]$ 的异或结果，可以通过 $[1, r]$ 和 $[1, l – 1]$ 的异或结果得出：