给一个数组,求出区间最大异或和
01字典树的典型应用,不过这个不是求和某个数x异或的最大值,而是要求出区间,区间的问题我们可以转成前缀和,比如查询与pre[2]异或最大的值,然后用这个求出的异或pre[2]就是3-k这一段的异或和了,然后为了保持查询的索引一定是再右边,所以一边扫查询一边插入新的(再后面的前缀和)
有一个坑点,不能从32位开始,要从31开始,32就会wa…
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+50;
int tree[33*N][2];
int a[33*N];
int pre[N];
int cnt;
int x,n;
void init(){
memset(tree,0,sizeof(tree));
memset(a,0,sizeof(a));
cnt=0;
}
void insert(int x,int p){
int root=0;
for(int i=31;i>=0;i--){
int id=(x>>i)&1;
if(!tree[root][id]){
tree[root][id]=++cnt;
}
root=tree[root][id];
}
a[root]=p;
}
int query(int x){
int root=0;
for(int i=31;i>=0;i--){
int id=(x>>i)&1;
if(tree[root][id^1]){
root=tree[root][id^1];
}
else{
root=tree[root][id];
}
}
return a[root];
}
int main(void){
printf("%d %d\n",2147483647>>32,2147483647>>31);
scanf("%d",&n);
init();
for(int i=1;i<=n;i++){
scanf("%d",&x);
pre[i]=pre[i-1]^x;
}
insert(pre[0],0);
int Max=0;
for(int i=1;i<=n;i++){
int k=query(pre[i]);
//printf("%d %d\n",ans,pre[i]);
Max=max(Max,pre[i]^pre[k]);
insert(pre[i],i);
}
printf("%d\n",Max);
return 0;
}