位或例題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，時間複雜度對比顯而易見。