本文涉及知識點

位運算、狀態壓縮、枚舉子集匯總

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?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)$,遞推式 ：$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++**實現。