XOR Queries of a Subarray
Problem
Given an array arr and a list of queries, where each query is [l, r], return for each query the XOR of arr[l], arr[l+1], …, arr[r].
arr = [1, 3, 4, 8], queries = [[0,1],[1,2],[0,3],[3,3]][2, 7, 14, 8]def xor_queries(arr, queries):
P = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
P[i + 1] = P[i] ^ x
return [P[r + 1] ^ P[l] for l, r in queries]function xorQueries(arr, queries) {
const P = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) P[i + 1] = P[i] ^ arr[i];
return queries.map(([l, r]) => P[r + 1] ^ P[l]);
}class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
int n = arr.length;
int[] P = new int[n + 1];
for (int i = 0; i < n; i++) P[i + 1] = P[i] ^ arr[i];
int[] out = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
out[i] = P[queries[i][1] + 1] ^ P[queries[i][0]];
}
return out;
}
}vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
int n = arr.size();
vector<int> P(n + 1, 0);
for (int i = 0; i < n; i++) P[i + 1] = P[i] ^ arr[i];
vector<int> out;
for (auto& q : queries) out.push_back(P[q[1] + 1] ^ P[q[0]]);
return out;
}Explanation
This is the prefix-sum idea but with XOR instead of addition. We precompute a prefix-XOR array once, then every query is answered with a single XOR of two values.
Build P so that P[i+1] = P[i] ^ arr[i], meaning P[i] is the XOR of the first i elements. The reason this works is that XOR is its own inverse: x ^ x = 0, so anything XORed twice cancels out.
For a query [l, r] we return P[r+1] ^ P[l]. The shared front part (everything before l) appears in both terms and cancels, leaving exactly the XOR of arr[l..r].
Example: arr = [1,3,4,8] gives P = [0,1,2,6,14]. Query [0,1] is P[2] ^ P[0] = 2 ^ 0 = 2, and query [1,2] is P[3] ^ P[1] = 6 ^ 1 = 7.
Building P is O(n) and each of the q queries is O(1), for O(n + q) overall.