一、题目
1、原题链接
3485. 最大异或和
2、题目描述
给定一个非负整数数列 a，初始长度为 N。
请在所有长度不超过 M 的连续子数组中，找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意：子数组可以为空。
输入格式
第一行包含两个整数 N,M。
第二行包含 N 个整数，其中第 i 个为 ai。
输出格式
输出可以得到的子数组异或和的最大值。
数据范围
对于 20% 的数据，1≤M≤N≤100
对于 50% 的数据，1≤M≤N≤1000
对于 100% 的数据，1≤M≤N≤105,0≤ai≤231−1
输入样例：
3 2
1 2 4
1
2
输出样例：
6
1
二、解题报告
思路来源：y总讲解视频
y总yyds
1、思路分析
数据范围为10^5，时间复杂度应控制在O(nlogn)
（1）我们知道一个数异或本身等于0，所以我们可以计算前r个数的异或值记为s[r]，计算前l-1个数的异或值记为s[l-1]（l<=r）。那么s[r]^s[l-1]，就相当于已经将前r个数异或，然后再异或上前l-1个数，所以前l-1个数异或了两次，值为0，仅仅剩下了从[l,r]的数的异或值，所以我们可以利用s[r]^s[l-1]来计算区间[l,r]上的所有数的异或值，类似前缀和算法。
（2）由（1）将s[i]（前i个数的异或值（0<=i<=n））二进制的每位数插入Tire树（可以想成Tire树有两个分枝，左0右1，每插入一个数就按它的每位数值向外延伸）中，同时记录Tire树中每个点（或分枝点）的出现次数。
（3）每当查找一个异或最大的两个数时，先从高位到低位遍历其中一个数的二进制的所有位的数，可以利用贪心，每次尽量从Tire树中，找到与当前位相异的分枝往下延伸，寻找数；如果不存在与当前位不同的数，则往与该位相同的分枝向下延伸，直至遍历完该数的每一个二进制位。
（4）区间中的数不能超过m个，所以每次在遍历区间左端点时，要保证区间内的数小于等于m个，（类似滑动窗口），如果当前区间中（即子数组中的数）大于m个，就将前面的数删掉。
（5）模拟上述过程，找到s数组中，某满足题目范围的两个数异或值的最大值输出即可。
2、时间复杂度
时间复杂度为O(n*31)
3、代码详解
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010,M=N*31;
int son[M][2],cnt[M],idx; //son[i][]存储第i个点的分枝（0或1），cnt[]记录每个结点的分枝数（再所有数中出现次数），idx存储点的编号（0号点既是根结点又是空节点）
int a[M],s[M]; //s[i]存储前i个数的异或值
int n,m;
int ans;
//从Tire树中添加一个数
void insert(int x){
int p=0; //p从根结点开始
for(int i=30;i>=0;i--){ //将x二进制的每一位插入Tire树中
int u=x>>i&1; //从高位到低位依次获取x的每一位数
if(!son[p][u]) son[p][u]=++idx; //如果某位数字不存在，则创建出来
p=son[p][u]; //否则，继续往下分枝，插入后边位置的数字
cnt[p]++; //将其每位数字的出现次数+1
}
}
//从Tire树中删除一个数
void move(int x){
int p=0; //p从根结点开始
for(int i=30;i>=0;i--){ //将x二进制的每一位插入Tire树中
int u=x>>i&1; //从高位到低位依次获取x的每一位数
p=son[p][u]; //依次遍历x的二进制的每一位数
cnt[p]--; //将其每位数字的出现次数-1
}
}
//查询与x异或值最大的数，并返回
int query(int x){
int p=0,res=0; //从根结点开始，res记录与x异或值最大的数
for(int i=30;i>=0;i--){
int u=x>>i&1; //从高位到低位依次遍历x的每位数字
if(cnt[son[p][!u]]){ //如果存在与该位数字相异的数，则走向该数，再遍历后面的数字
p=son[p][!u];
res=res*2+!u; //将已经得到的高位的数左移一位（乘2），再加上该位数字，即是当前所有位数字组成的数的十进制数的值
}
else{ //否则只能走向与该位数字相同的数，走向该分枝，再遍历后面的数字
p=son[p][u];
res=res*2+u; //同上
}
}
return res;
}
int main(){
cin>>n>>m;
//因为存在子数组为空的的情况，所以先将数0插入Tire树中
insert(s[0]);
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^a[i]; //计算前i个数异或的值
}
for(int i=1;i<=n;i++){
if(i-1-m>=0) move(s[i-1-m]); //s[i]^s[i-m-1]中i-m是左端点能够到达的最远地方（因为如果以i为右端点的区间中最多存在m个数，所以区间左端点最多到i-m+1，所以就是要求区间[i-m+1,i]上的m个数的异或值，也就是求s[i]^s[i-m]，枚举s数组时，如果i-m-1也在区间中了，就要删掉它，因为最远只能到i-m）
ans=max(ans,s[i]^query(s[i])); //从满足条件的区间中查找与是s[i]异或值最大是多少
insert(s[i]); //将s[i]插入Tire树中
}
cout<<ans;
return 0;
}
三、知识风暴
前缀和
如果记s[l-1]为前l-1个数的和，s[r]为前r个数的和（l<=r），则区间[l,r]上的数的和为s[r]-s[l-1]，可以据此快速计算给定区间中所有数的和。
Tire树
高效存储和查找字符串集合的数据结构
贪心算法
贪心用于解决最优解问题，可以解决从局部最优可以找到整体最优的问题。
