#3782. 题目3-最大子数组异或和-前缀异或和
题目3-最大子数组异或和-前缀异或和
【题目描述】
给定一个非负整数数组,求其中任一连续子数组的异或和的最大值。
提示:设 pre[i] 为前缀异或和,则任意子数组 [L, R] 的异或和为 pre[R] ^ pre[L-1]。问题转化为:从所有前缀异或值中选取一对,使得它们的异或值最大。可以利用字典树(Trie)来高效求解。
【输入格式】
- 第一行包含一个正整数 n(1 ≤ n ≤ 10^5)。
- 第二行包含 n 个非负整数,数组中每个数不超过 10^9。
【输出格式】
- 输出一个整数,表示最大子数组异或和。
【样例输入】
5
3 8 2 6 4
【样例输出】
15
【说明】
通过构造前缀异或数组并利用 Trie 优化查找,可以在 O(n·logC) 的时间内求出答案(C 为数值范围)。