当前位置：首页 > news >正文

【位运算】查询子数组最大异或值|2693

news 2025/8/18 10:22:07

本文涉及知识点

位运算、状态压缩、枚举子集汇总

3277. 查询子数组最大异或值

给你一个由 n 个整数组成的数组 nums，以及一个大小为 q 的二维整数数组 queries，其中 queries[i] = [li, ri]。

对于每一个查询，你需要找出 nums[li…ri] 中任意子数组的最大异或值。

数组的异或值需要对数组 a 反复执行以下操作，直到只剩一个元素，剩下的那个元素就是异或值：

对于除最后一个下标以外的所有下标 i，同时将 a[i] 替换为 a[i] XOR a[i + 1] 。
移除数组的最后一个元素。
返回一个大小为 q 的数组 answer，其中 answer[i] 表示查询 i 的答案。

示例 1：

输入： nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

输出： [12,60,60]

解释：

在第一个查询中，nums[0…2] 的子数组分别是 [2], [8], [4], [2, 8], [8, 4], 和 [2, 8, 4]，它们的异或值分别为 2, 8, 4, 10, 12, 和 6。查询的答案是 12，所有异或值中的最大值。

在第二个查询中，nums[1…4] 的子数组中最大的异或值是子数组 nums[1…4] 的异或值，为 60。

在第三个查询中，nums[0…5] 的子数组中最大的异或值是子数组 nums[1…4] 的异或值，为 60。

示例 2：

输入： nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

输出： [7,14,11,14,5]

解释：

下标 nums[li…ri] 最大异或值子数组子数组最大异或值
0 [0, 7, 3, 2] [7] 7
1 [7, 3, 2, 8, 5] [7, 3, 2, 8] 14
2 [3, 2, 8] [3, 2, 8] 11
3 [3, 2, 8, 5, 1] [2, 8, 5, 1] 14
4 [5, 1] [5] 5

提示：

1 <= n == nums.length <= 2000
$0 <= nums[i] <= 2^{31} - 1$
$1 <= q == queries.length <= 10^5$
queries[i].length == 2
queries[i] = [li, ri]
0 <= li <= ri <= n - 1

位运算

长度为1的数组异或值： $a_0$
长度为2的数组的异或值: $a0⊕a1a_0 \oplus a_1$
长度为3的数组的异或值： $a0⊕a1⊕a1⊕a2a_0 \oplus a_1 \oplus a_1 \oplus a_2$ 即 $a_0 a_1^2 a_2$ 异或两次，相互抵消，即 $a 0 a 2$
长度为4的数组的异或值： $a_0a_1)(a_2a_3)$ 即 $a_0a_1a_2a_3$
长度为5的数组的异或值： $a_0a_1)(a_1a_2)(a_2a_3)(a_3a_4)$ 即 $a_0a_4$
长度为6的数组的异或值： $a_0a_1a_4a_5$
长度为7的数组的异或值： $a_0a_2a_4a_6$
没有头绪，看题解,有递推式 $f(0,r)=f(0,r−1)⊕f(1,r)f(0,r)=f(0,r-1)\oplus f(1,r)$ ,
自己思考的证明。
性质一：f(a)= $⨁(ai×bi),bi∈0,1\bigoplus (a_i \times b_i),bi \in{0,1}$ ,因为 $a_i$ 异或两次会抵消。
性质二： $e[i]=a[i]×c[i]→f(e)==f(a)⊕f(c)e[i]=a[i]\times c[i] \rightarrow f(e)== f(a) \oplus f(c)$ 。如果 $0 == b_i，左式和右式都不包括a_i,c_i;如果1==b_i，左右式都包括一个a_i,c_i。$
性质三：长度n的数组a，操作一次后：
$f(a0a1⋯an−1)=f((a0⊕a1)(a1⊕a2)(an−2⊕an−1)f(a_0 a_1 \cdots a_{n-1})=f((a_0 \oplus a_1) (a_1 \oplus a_2) (a_{n-2} \oplus a_{n-1})$ ，根据性质二递推式得证。

实现

vMax1[left][r] = $max⁡f(left⋯r,r)\max f(left\cdots r,r)$ ,递推式： $v M a x 1 [l e f t] [r] = ma x (v M a x 1 [l e f t + 1] [r], f (l e f t, r))$ 。
vMax[left][r] = $max⁡f(left1,r1),left≤left1≤r,left1≤r1≤r\max f(left1,r1),left \le left1 \le r,left1 \le r1 \le r$ vMax[left][r] = max(vMax[left][r-1] ,vMax1[left,r])

代码

核心代码

class Solution {public:vector<int> maximumSubarrayXor(vector<int>& nums, vector<vector<int>>& queries) {const int N = nums.size();vector<vector<int>> f(N, vector<int>(N));for (int i = 0; i < N; i++) { f[i][i] = nums[i]; }auto vMax1 = f, vMax = f;for (int len = 2; len <= N; len++) {for (int i = 0; i + len <= N; i++) {const int end = i + len - 1;f[i][end] = f[i][end - 1] ^ f[i + 1][end];vMax1[i][end] = max(vMax1[i+1][end], f[i][end]);vMax[i][end] = max(vMax[i][end - 1], vMax1[i][end]);}}vector<int> ans;for (const auto& v : queries) {ans.emplace_back(vMax[v[0]][v[1]]);}return ans;}};

单元测试

vector<int> nums;vector<vector<int>> queries;TEST_METHOD(TestMethod11){nums = { 2,8,4,32,16,1 }, queries = { {0,2},{1,4},{0,5} };auto res = Solution().maximumSubarrayXor(nums, queries);AssertEx({ 12,60,60 }, res);}TEST_METHOD(TestMethod12){nums = { 0,7,3,2,8,5,1 }, queries = { {0,3},{1,5},{2,4},{2,6},{5,6} };auto res = Solution().maximumSubarrayXor(nums, queries);AssertEx({ 7,14,11,14,5 }, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
员工说：技术至上，老板不信；投资人的代表说：技术至上，老板会信。
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功