1. 结构

2. 用途

3. 应用

3.1 子数组的最大异或和

题目：
数组异或和的定义：把数组中所有的值异或起来的到值
给定一个int数组，其中有正有负，有0，求其中子数组的最大异或和
eg:
{3}, 最大异或和就是3
{3,-28,-29,2}, 子数组为{-28,-29}，最大异或和为7

3.1.1 暴力解

    private int process(int[] nums){
        if(nums.length == 1){
            return nums[0];
        }
        //子数组问题，遍历以i结尾的所有子数组，比大小,arr[...i]
        int ans=0;
        for (int i = 0; i < nums.length; i++) {
            for (int start = 0; start <= i; start++) {
                int sum=0;
                //对arr[start...i]的数子进行累加，比大小
                for (int j = start; j <= i; j++) {
                    sum ^= nums[j];
                }
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }

3.1.2 根据异或和的性质进行优化

思路：
xorSum[0...s] ^ xorSum[s+1 .... i] = xorSum[0...i]
=>
xorSum[s .... i] = xorSum[0...s-1] ^ xorSum[0...i]

    private int processUpgrade(int[] nums){
        if(nums.length == 1){
            return nums[0];
        }
        //记录xorSum[0...i]的异或和
        int[] preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] =  preSum[i-1] ^ nums[i];
        }

        //子数组问题，遍历以i结尾的所有子数组，比大小,arr[...i]
        int ans=0;
        for (int i = 0; i < nums.length; i++) {
            for (int start = 0; start <= i; start++) {
                //对arr[start...i]的数子进行累加，比大小
                int sum= (start -1 == -1) ? (0 ^ preSum[i]) : (preSum[start-1] ^ preSum[i]);
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }

3.1.3 利于前缀树的路径进行贪心优化

    private int processTrie(int[] nums){
        if(nums.length == 1){
            return nums[0];
        }

        //记录xorSum[0...i]的异或和
        int[] preSum = new int[nums.length];
        preSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            preSum[i] =  preSum[i-1] ^ nums[i];
        }

        NumTrie numTrie = new NumTrie();
        numTrie.add(0);

        //子数组问题，遍历以i结尾的所有子数组，比大小,arr[...i]
        int ans=0;
        for (int i = 0; i < nums.length; i++) {
            //通过前缀数，中记录了0，0-1，0-2，...0-i的前缀合路径，返回这些路径中和（当前前缀和）结合最大的值
            int preMax = numTrie.maxXor(preSum[i]);
            ans = Math.max(ans, preMax);
            //将当前前缀和，加入到前缀树路径
            numTrie.add(preSum[i]);
        }
        return ans;
    }

结构和方法：

    public static class Node{
        public Node[] nexts = new Node[2];
    }

    public static class  NumTrie{

        public Node head = new Node();

        public void add(int num){
            Node cur = head;
            //从高位开始取，构建path，需要右移
            for (int i = 31; i >0; i--) {
               int path = (num >> i) & 1;
                //没有路径创建，又的话就继续遍历添加
                cur.nexts[path] =  head.nexts[path] == null ? new Node() : head.nexts[path];
                cur = cur.nexts[path];
            }

        }

        /**
         * 将sum走最优路径后，返回最大异或和
         * @param sum
         * @return
         */
        public int maxXor(int sum){
            Node cur = head;
            int ans = 0;
            //从高位开始取，构建path，需要右移
            for (int i = 31; i >0; i--) {
                int path = (sum >> i) & 1;
                //贪心：找最佳路径，如果是符号位就是一样的，否则取异或的
                int best = i==32 ? path : path^1;
                //实际能走的路径
                best = cur.nexts[path]!=null ? best : best^1;
                //best ^ path 为计算出来的最大位值，还需要移动回去
                ans = ans | (best ^ path) << i;
            }
            return ans;
        }

    }

前缀树