Log inSign up
mediumLeetCodeNot Started

XOR Queries of a Subarray

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Bit Manipulation
Solve on LeetCode
Lesson

Problem Statement

You are given an array arr of positive integers and an array queries where queries[i] = [left_i, right_i].

For each query i, compute the XOR of elements from left_i to right_i (i.e., arr[left_i] ^ arr[left_i + 1] ^ ... ^ arr[right_i]).

Return an array containing the result for each query.

Example 1 · Example 1: Multiple Subarray Queries:

Input: arr = [1, 3, 4, 8], queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
Output: [2, 7, 14, 8]
Explanation: - [0, 1] -> 1 ^ 3 = 2 - [1, 2] -> 3 ^ 4 = 7 - [0, 3] -> 1 ^ 3 ^ 4 ^ 8 = 14 - [3, 3] -> 8

Example 2 · Example 2: All Identical Elements:

Input: arr = [4, 8, 2, 10], queries = [[2, 3]]
Output: [8]
Explanation: 2 ^ 10 = 8.

Constraints:

  • 1 <= arr.length, queries.length <= 3 * 104
  • 1 <= arr[i] <= 109
  • queries[i].length == 2
  • 0 <= left_i <= right_i < arr.length

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Adapt the prefix sum pattern to non-additive algebraic operators like bitwise XOR.
  • Understand why self-canceling properties enable prefix window isolation.
  • Achieve optimal O(1) query time complexity.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Multiple static range queries for XOR sums.
  • No element updates between queries.
  • Inverse property of XOR matches prefix reduction.

Algorithmic Decision Tree:

  • Build prefix array pref[i] = pref[i - 1] ^ arr[i].
  • For each query [L, R]: ans = L == 0 ? pref[R] : pref[R] ^ pref[L - 1].

Connected Patterns:

Range Sum Query - ImmutableXOR of All Numbers in an ArraySubsets XOR Sum

1. Per-Query Linear Iteration

Intuition

For each query [l, r], loop index i from l to r and XOR elements together.

When to apply: When there is only one query or memory cannot be allocated.

Algorithm

  1. Step 1: Initialize res list.
  2. Step 2: For each query [l, r]: cur = 0; loop i from l to r: cur ^= arr[i].
  3. Step 3: Append cur to res.
  4. Step 4: Return res.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6vector<int> xorQueriesBrute(const vector<int>& arr, const vector<vector<int>>& queries) {
7 vector<int> res;
8 res.reserve(queries.size());
9 for (const auto& q : queries) {
10 int l = q[0], r = q[1];
11 int cur = 0;
12 for (int i = l; i <= r; ++i) {
13 cur ^= arr[i];
14 }
15 res.push_back(cur);
16 }
17 return res;
18}
19
20int main() {
21 vector<int> arr = {1, 3, 4, 8};
22 vector<vector<int>> queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
23 auto res = xorQueriesBrute(arr, queries);
24 for (int v : res) cout << v << " ";
25 cout << endl; // 2 7 14 8
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(q * n)
  • Space complexity: O(1) auxiliary space

2. Segment Tree for Range XOR

Intuition

Construct a segment tree where each tree node stores the bitwise XOR of its range. A range query [l, r] takes O(log n) time by combining disjoint canonical segments.

When to apply: When elements in arr are dynamically updated between queries.

Algorithm

  1. Step 1: Build segment tree of size 4n with tree[node] = tree[2*node] ^ tree[2*node + 1].
  2. Step 2: For each query [l, r], query segment tree in O(log n).
  3. Step 3: Return results.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class SegTree {
7 vector<int> tree;
8 int n;
9
10 void build(const vector<int>& arr, int node, int l, int r) {
11 if (l == r) {
12 tree[node] = arr[l];
13 return;
14 }
15 int mid = l + (r - l) / 2;
16 build(arr, 2 * node, l, mid);
17 build(arr, 2 * node + 1, mid + 1, r);
18 tree[node] = tree[2 * node] ^ tree[2 * node + 1];
19 }
20
21 int query(int node, int l, int r, int ql, int qr) {
22 if (ql <= l && r <= qr) return tree[node];
23 if (r < ql || l > qr) return 0;
24 int mid = l + (r - l) / 2;
25 return query(2 * node, l, mid, ql, qr) ^ query(2 * node + 1, mid + 1, r, ql, qr);
26 }
27
28public:
29 SegTree(const vector<int>& arr) {
30 n = arr.size();
31 tree.resize(4 * n, 0);
32 build(arr, 1, 0, n - 1);
33 }
34
35 int queryRange(int l, int r) {
36 return query(1, 0, n - 1, l, r);
37 }
38};
39
40vector<int> xorQueriesSegTree(const vector<int>& arr, const vector<vector<int>>& queries) {
41 SegTree st(arr);
42 vector<int> res;
43 for (const auto& q : queries) {
44 res.push_back(st.queryRange(q[0], q[1]));
45 }
46 return res;
47}
48
49int main() {
50 vector<int> arr = {1, 3, 4, 8};
51 vector<vector<int>> queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
52 auto res = xorQueriesSegTree(arr, queries);
53 for (int v : res) cout << v << " ";
54 cout << endl; // 2 7 14 8
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(n + q log n)
  • Space complexity: O(4n) segment tree memory

3. Prefix XOR Array

Intuition

Compute pref[i] = pref[i - 1] ^ arr[i] for all elements. For each query [l, r]: if l == 0, the answer is pref[r]. Otherwise, the answer is pref[r] ^ pref[l - 1].

When to apply: Optimal canonical solution for static subarray XOR queries.

Algorithm

  1. Step 1: Compute pref array of length n where pref[i] = (i == 0 ? arr[0] : pref[i - 1] ^ arr[i]).
  2. Step 2: Allocate res array of size queries.length.
  3. Step 3: For each query [l, r]: res[k] = (l == 0 ? pref[r] : pref[r] ^ pref[l - 1]).
  4. Step 4: Return res.

Prefix XOR Trace: arr = [1, 3, 4, 8]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Compute prefix table
Visual state
Values and pointers at this exact step
pointers
S
1
2
6
14
0
1
2
↑ pref table
3
Check / comparison
pref built
Decision / next transition
Preprocessing complete in O(n).
Why this step matters

Step 1: Compute prefix table. pref[0] = 1, pref[1] = 13 = 2, pref[2] = 24 = 6, pref[3] = 68 = 14. pref = [1, 2, 6, 14].

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
9 int n = arr.size();
10 vector<int> pref(n);
11 pref[0] = arr[0];
12 for (int i = 1; i < n; ++i) {
13 pref[i] = pref[i - 1] ^ arr[i];
14 }
15
16 vector<int> res;
17 res.reserve(queries.size());
18 for (const auto& q : queries) {
19 int l = q[0], r = q[1];
20 if (l == 0) {
21 res.push_back(pref[r]);
22 } else {
23 res.push_back(pref[r] ^ pref[l - 1]);
24 }
25 }
26 return res;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> arr = {1, 3, 4, 8};
33 vector<vector<int>> queries = {{0, 1}, {1, 2}, {0, 3}, {3, 3}};
34 auto res = sol.xorQueries(arr, queries);
35 for (int v : res) cout << v << " ";
36 cout << endl; // 2 7 14 8
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(n + q)
  • Space complexity: O(n) auxiliary

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Linear Scan Per QueryO(q * n)O(1) auxiliaryFor every query [L, R], run a loop from L to R computing cumulative XOR.Repeated range traversal.
2.Better — Segment Tree for Range XORO(n + q log n)O(n)Build a segment tree over arr storing XOR sums in internal nodes.Tree traversal per query.
3.Optimal — Prefix XOR ArrayOptimalO(n + q)O(n) auxiliaryCompute prefix XOR table in O(n); answer each query in O(1) via pref[R] ^ pref[L - 1].Output array population.

Common Pitfalls & Crucial Edge Cases

Iterating through [L, R] for each query

Takes O(N * Q) time and causes TLE when N = 3 * 104 and Q = 3 * 104.

Off-by-one in prefix array

Forgetting that prefix array should have size N + 1 with prefix[0] = 0.

Using prefix subtraction instead of XOR

Range XOR is prefix[R + 1] ^ prefix[L], NOT subtraction.

Crucial Edge Cases to Validate:

  • Query covers single element (L == R) — Returns arr[L].
  • Query starts at 0 (L == 0) — Returns prefix[R + 1] ^ prefix[0] = prefix[R + 1] (since prefix[0] = 0).
  • Entire array query (L = 0, R = N - 1) — Returns XOR of all elements.
  • Q = 10^5 queries — Solved in O(1) per query instead of timing out with O(N * Q).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Draw the direct analogy between Prefix Sums for range sum queries and Prefix XORs for range XOR queries.
  2. Explain the self-inverse property: A ^ B ^ A = B.
  3. Mention that this can be computed in-place in arr to achieve O(1) auxiliary space (excluding the output array).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How can prefix XORs answer range XOR queries [L, R] in O(1) time?

2.What is the time complexity to answer Q queries on an array of size N using prefix XORs?

3.Why does the prefix XOR technique work identically to the prefix sum technique?

Back to DSA Sheet