public class Solution {
    /*
     * @param : the array
     * @return: the max xor sum of the subarray in a given array
     */
    class TrieNode{
        public int label;
        public TrieNode[] children;
        TrieNode(int label){
            this.label = label;
            this.children = new TrieNode[2];
        }
    }
    public int maxXorSubarray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int max = 0;
        int pre_xor = 0;
        TrieNode root = new TrieNode(0);
        for(int i=0;i<nums.length;i++){
            pre_xor ^= nums[i];
            insert(root, pre_xor);
            max = Math.max(max, searchAndFindMax(root, pre_xor));
        }
        return max;
    }

    private void insert(TrieNode root, int num){
        TrieNode cur = root;
        for(int i=31;i>=0;i--){
            int bit = num >> i & 1;
            if(cur.children[bit] == null){
                cur.children[bit] = new TrieNode(bit);
            }
            cur = cur.children[bit];
        }
    }

    private int searchAndFindMax(TrieNode root, int num){
        TrieNode cur = root;
        int res = 0;
        for(int i=31;i>=0;i--){
            int bit = num >> i & 1;
            if(cur.children[1-bit] != null){
                res |= 1 << i;
                cur = cur.children[1-bit];
            }else{
                cur = cur.children[bit];
            }
        }
        return res;
    }
}