本文涉及知识点

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

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的数组的异或值:$a_0\oplus a_1$
长度为3的数组的异或值：$a_0\oplus a_1\oplus a_1\oplus a_2$即$a_0{a}_1^2{a}_2$异或两次，相互抵消，即$a0a2$
长度为4的数组的异或值：$(a_0{a}_1)(a_2{a}_3)$即$a_0{a}_1{a}_2{a}_3$
长度为5的数组的异或值：$(a_0{a}_1)(a_1{a}_2)(a_2{a}_3)(a_3{a}_4)$即$a_0{a}_4$
长度为6的数组的异或值：$a_0{a}_1{a}_4{a}_5$
长度为7的数组的异或值：$a_0{a}_2{a}_4{a}_6$
没有头绪，看题解,有递推式$f(0,r)=f(0,r-1)\oplus f(1,r)$,
自己思考的证明。
性质一：f(a)=$⨁(a_i\times b_i),bi\in 0,1$,因为$a_i$异或两次会抵消。
性质二：$e[i]=a[i]\times c[i]\to f(e)==f(a)\oplus f(c)$。如果$0==b_i，左式和右式都不包括a_i,c_i;如果1==b_i，左右式都包括一个a_i,c_i。$
性质三：长度n的数组a，操作一次后：
$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\cdots r,r)$,递推式 ：$vMax1[left][r]=max(vMax1[left+1][r],f(left,r))$。
vMax[left][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);}

扩展阅读

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

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。