Trie implementation for XOR problem

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Created by arpit on 16/12/16.
 */
class NikitoshAndXor {

    static final int MAX=400000;
    static int a[]=new int[MAX],maxPrefix[]=new int[MAX],maxSuffix[]=new int[MAX];

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n;
        String s[];
        n=Integer.parseInt(br.readLine());
        s=br.readLine().split("\\s");

        for (int i = 0; i < n; i++) {
            a[i]=Integer.parseInt(s[i]);
            maxPrefix[i]=a[i];
            maxSuffix[i]=a[i];
        }
        System.out.println(solve(n));

    }

    private static long solve(int n) {
        fillMaxPrefix(n);
        fillMaxSuffix(n);
        long ans=Integer.MIN_VALUE;

        for (int i = 0; i < (n - 1); i++)
            ans = Long.max(ans, maxPrefix[i] + maxSuffix[i + 1]);

        return ans;
    }

    private static void fillMaxSuffix(int n) {
        Trie suffixTrie=new Trie();
        int suff=a[n-1];
        suffixTrie.insert(0);
        suffixTrie.insert(a[n-1]);
        for (int i = n-2; i>=0; i--) {
            suff^=a[i];
            maxSuffix[i]=Integer.max(maxSuffix[i+1], suffixTrie.query(suff));
            suffixTrie.insert(suff);
        }
    }

    private static void fillMaxPrefix(int n) {
        Trie prefixTrie = new Trie();
        int pre=a[0];
        prefixTrie.insert(0);
        prefixTrie.insert(a[0]);
        for (int i = 1; i < n; i++) {
            pre^=a[i];
            //System.out.println(prefixTrie.query(pre));
            maxPrefix[i]=Integer.max(maxPrefix[i-1],prefixTrie.query(pre));
            prefixTrie.insert(pre);
        }
    }

    static class Trie{

        TrieNode root;

        public Trie() {
            root=new TrieNode();
        }

        class TrieNode{
            int val;
            TrieNode[]child;

            public TrieNode() {
                child=new TrieNode[2];
            }
        }
        void insert(int key){

            TrieNode temp=root;
            for (int i = 31; i>=0; i--) {
                int currBit;
                if ((key&(1<<i))>=1)currBit=1;
                else currBit=0;

                if (temp.child[currBit]!=null){
                    temp=temp.child[currBit];
                }
                else{
                    temp.child[currBit]=new TrieNode();
                    temp=temp.child[currBit];
                }
            }
            temp.val=key;
        }

        int query(int key){
            TrieNode temp=root;
            for (int i = 31; i>=0; i--) {
                int currBit;
                if ((key&(1<<i))>=1)currBit=1;
                else currBit=0;

                if (temp.child[1-currBit]!=null){
                    temp=temp.child[1-currBit];
                }
                else if (temp.child[currBit]!=null){
                    temp=temp.child[currBit];
                }
                else break;
            }
            return temp.val^key;
        }
    }
}