【题解】子数组的最大异或和

记 表示数组前 个数的异或和，就是区间的异或和
那如果想知道以 位置结尾的子数组的最大异或和，只需要知道 和 中的数异或的最大值就可以了。
（即这些区间异或和的最大值）
那怎么样快速地知道 和 中的数异或和的最大值呢?
我们利用前缀树的结构，对每一个，从最高位到最低位判断。这里需要注意一下，因为我们想让异或和最大，所以我们希望符号位是0，即异或出的数值是正数，然后其他位置我们期望数值为1
所以对于最高位来说，我们希望和的这一位相同，其他位置我们希望和的这一位不同。
走完前缀树以后，就维护出了以位置结尾的子数组的最大异或和，然后把当前的数加到前缀树里。

#include<iostream>
using namespace std;
struct node;
struct node{
    node* num[2];
};
node * head;
void add(int num){//把num加到前缀树里
    node * now = head;
    for(int i = 31 ; i >= 0 ; i--){
        int t = 1&(num>>i);//取num的第i位
        if(now->num[t] == NULL){
            now->num[t] = new node{NULL,NULL};
            now = now->num[t];
        }
        else{now = now->num[t];}
    }
}
const int MAXN = 1e5+10;
int main(){
    int n; cin >> n;
    int XOR[MAXN]={0};
    for(int i =1 ; i <= n ; i++){//求前缀异或和
        int t; cin >>t;
        XOR[i] = t^XOR[i-1];
    }
    head = new node{NULL,NULL};
    node * now = head;
    add(XOR[1]);
    int maxn = XOR[1];
    for(int i = 2 ; i <= n ; i++){
        now = head;
        int ans = 0;
        for(int j = 31 ; j >= 0 ; j--){
            int t = 1&(XOR[i]>>j);
            int target= !t;//希望和0还是和1异或
            if(j == 31){target = t;}
            if(now->num[target]!=NULL){
                now=now->num[target]; 
                ans=ans|((target^t)<<j); 
            }
            else{
                 now = now->num[!target];
                 ans=ans|((!target^t)<<j);
            }
        }
        add(XOR[i]);
        maxn = max(maxn,ans);
    }
    cout<<maxn<<endl;
    return 0;
}