给一个数组,求出区间最大异或和
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;
}