Bit Manipulation - XOR Queries of a Subarray

Given an array arr and queries where queries[i] = [left, right], return the XOR of elements from arr[left] to arr[right] for each query.

Input: arr=[1,3,4,8], queries=[[0,1],[1,2],[0,3],[3,3]] → Output: [2,7,14,8]

Input: arr=[4,8,2,10], queries=[[2,3],[1,3],[0,0],[0,3]] → Output: [8,0,4,4]

Precompute prefix XOR array where prefix[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1]. Then XOR of arr[l..r] = prefix[r+1] XOR prefix[l].

Build prefix XOR: prefix[0]=0, prefix[i]=prefix[i-1]^arr[i-1].
For each query [l, r]: answer = prefix[r+1] ^ prefix[l].
This works because a^a=0, so all elements before index l cancel out.

class Solution { public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[] prefix = new int[n + 1]; for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i]; int[] result = new int[queries.length]; for (int i = 0; i < queries.length; i++) result[i] = prefix[queries[i][1] + 1] ^ prefix[queries[i][0]]; return result; } }

Time Complexity: O(N + Q)
Space Complexity: O(N) for prefix array