位或例题Java 暴力法和前缀异或法

我写的垃圾暴力法：

public static int[] xorQueries(int[] arr, int[][] queries) {             int i = queries.length;             int []querr= new int[i];             int idx = 0;             int num;             for (int [] s : queries) {                 num = 0;                 for (int d= s[0];d<=s[1];d++){                     num = arr[d]^num;                 }                 querr[idx] = num;                 idx++;             }             return querr;         }      

人家写的前缀异或法

public int[] xorQueries(int[] arr, int[][] queries) {             int n = arr.length;             int[] xors = new int[n + 1];             for (int i = 0; i < n; i++) {                 xors[i + 1] = xors[i] ^ arr[i];             }             int m = queries.length;             int[] ans = new int[m];             for (int i = 0; i < m; i++) {                 ans[i] = xors[queries[i][0]] ^ xors[queries[i][1] + 1];             }             return ans;         }      

它的原理是创建一个长度为arr.length+1的数组，每个元素n存放的是arr[0]连续位或到arr[n-1]，第一个元素定为0方便位或别的元素，0位或任何数=任何数，第2个元素存放的是arr[0]^arr[2-1]，这样以此存放。

首先为什么长度是arr.length+1呢，因为第一个元素必须是0，所以多了一位，其次为什么第一个必须是0呢，因为0位或任何数是等于任何数本身，目的就是当二维数组是{0,3}这样的值时，我们应该在arr数组数0-3也就是4个连续位或过去，而这个4个位或刚好存放在我们的数组第四个元素上，因为第一个元素是0，所以我们让第一个元素位或第4个元素就返回了正确的值，也就是这个部分

xors[queries[i][0]] ^ xors[queries[i][1] + 1]; 此时queries[i][0]是二维数组的0 queries[i][1]是二维数组的3，所以要+1，时间复杂度对比显而易见。