子数组的最大异或和（Trie字典树）

LintCode 炼码 - 更高效的学习体验子数组的最大异或和_牛客题霸_牛客网算法最大子数组异或和_异或值最大的子数组-CSDN博客这段代码是为了处理可能包含负数的整数数组而负数的最高位第 31 位是符号位。在求最大异或值时我们希望异或结果的数值尽可能大而符号位为 0 的结果一定是正数大于任何负数。因此对于符号位我们尽量让异或结果为 0即num和target的符号位相同所以target index。而对于其他位30 ~ 0我们希望异或结果为 1所以选择相反位target 1 - index。#include iostream #include limits #include new #include vector using namespace std; struct Trie { std::vectorTrie* next; int val; Trie() { val -1; next.resize(2, nullptr); } }; void insert(Trie* root, int num) { if (!root) { return; } for (int i 31; i 0; --i) { int index (num i) 1; if (!root-next[index]) { root-next[index] new (std::nothrow) Trie; } root root-next[index]; } root-val num; } int search(Trie* root, int num) { if (!root) { return -1; } for (int i 31; i 0; --i) { int index (num i) 1; int target 1 - index; if (i 31) { target index; } if (root-next[target]) { root root-next[target]; } else { root root-next[1 - target]; } } return root-val; } class Solution { public: Solution() { } int solve(std::vectorint nums) { Trie* root new (std::nothrow) Trie; int result -1; int prefix_sum 0; insert(root, 0); for (auto num : nums) { prefix_sum ^ num; insert(root, prefix_sum); int tmp search(root, prefix_sum); result max(result, tmp ^ prefix_sum); } return result; } }; int main() { int a, b; while (cin a) { // 注意 while 处理多个 case std::vectorint nums; nums.reserve(a); for (int i 0; i a; i) { cin b; //cout b : b endl; nums.push_back(b); } Solution sol; cout sol.solve(nums) endl; } } // 64 位输出请用 printf(%lld)