子数组的最大异或和

1. 对于符号位，我们希望找到一个与当前异或和状态相同的前缀异或和，因为同状态异或得0，可以使异或结果变成正数；
2. 对于非符号位，我们希望找到一个与当前异或和状态不同的前缀异或和，因为不同状态才能使得异或结果为1。

import java.util.Scanner;

class Node {
    public Node[] next = new Node[2];     // 每个节点表示整数的一个位，有0和1两个状态
}

class NumTrie {
    public Node head = new Node();
    public void add(int num) {
        Node cur = head;
        for(int move = 31; move >= 0; move--){
            int bit = (num >> move) & 1;    // 取出从右往左的第move位
            cur.next[bit] = cur.next[bit] == null? new Node(): cur.next[bit];
            cur = cur.next[bit];
        }
    }
    
    public int maxXOR(int num) {
        Node cur = head;
        int res = 0;
        for(int move = 31; move >= 0; move--){
            int bit = (num >> move) & 1;
            int expect = move == 31? bit: bit ^ 1;      // 当前位为符号位时，希望要走的路径与当前位相同
            expect = cur.next[expect] == null? expect ^ 1: expect;      // 期望路径不空才能走
            res |= (bit ^ expect) << move;     // 把res中这一位的状态改了
            cur = cur.next[expect];
        }
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int max = Integer.MIN_VALUE;
        int eor = 0;      // 前缀异或和
        NumTrie trie = new NumTrie();
        trie.add(0);
        for(int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            eor ^= arr[i];
            max = Math.max(max, trie.maxXOR(eor));     // 找到数组以arr[i]结尾时，最大的异或和
            trie.add(eor);
        }
        System.out.println(max);
    }
}