Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Prefix XOR
DSA

Prefix XOR

Understand how cumulative XOR values can efficiently solve range XOR and bitwise array problems.

Prefix XOR precomputes the XOR from the start to each index, enabling O(1) subarray XOR queries.

Its core idea:

XOR of subarray [l, r] = prefix[r] ^ prefix[l-1] — because XOR cancels itself (x ^ x = 0).

Focus on recognizing:

“XOR of subarray” + “Range query” = Prefix XOR

Core Template

Watch the prefix XOR of [3,5,2,7] build to [3,6,4,3], then xor(1..2) resolve as 4 ^ 3 = 7. Press ▶ to animate.

Prefix XOR (Build + O(1) Range Queries)

Precompute a prefix-XOR array X where X[i] is the XOR of the first i+1 elements, then answer any range XOR in O(1) via X[r] ^ X[l-1]. XOR's x ^ x = 0 property is what makes subtraction possible.

arr = [3,5,2,7]. Seed X[0]=3, then X[i] = X[i-1] ^ nums[i]. Watch the bit flips: 3^5 = 6 (011^101=110), 6^2 = 4, 4^7 = 3. Result X = [3,6,4,3]; the last cell is the XOR of everything. ('·' cells are not-yet-computed prefix entries.)

ARRAY VISUALIZER
Steps –
3
0
6
1
·
2
·
3
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        X[0] = nums[0]
                      
                        2
                        for i in 1..n-1:
                      
                        3
                          X[i] = X[i-1] ^ nums[i]
                      
public int xorQuery(int[] nums, int l, int r) {
    int n = nums.length;
    int[] prefix = new int[n];

    prefix[0] = nums[0];

    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] ^ nums[i];
    }

    if (l == 0) return prefix[r];
    return prefix[r] ^ prefix[l - 1];
}
def xor_query(nums, l, r):
    n = len(nums)
    prefix = [0] * n

    prefix[0] = nums[0]

    for i in range(1, n):
        prefix[i] = prefix[i - 1] ^ nums[i]

    if l == 0:
        return prefix[r]
    return prefix[r] ^ prefix[l - 1]
int xorQuery(vector<int>& nums, int l, int r) {
    int n = nums.size();
    vector<int> prefix(n);

    prefix[0] = nums[0];

    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] ^ nums[i];
    }

    if (l == 0) return prefix[r];
    return prefix[r] ^ prefix[l - 1];
}
function xorQuery(nums, l, r) {
  const n = nums.length;
  const prefix = Array(n);

  prefix[0] = nums[0];

  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] ^ nums[i];
  }

  if (l === 0) return prefix[r];
  return prefix[r] ^ prefix[l - 1];
}

Identical skeleton to prefix sum — only + becomes ^. That works because XOR is its own inverse.

Why It Works

Every element before l appears in both prefix[r] and prefix[l-1]:

prefix[r]     = a0 ^ a1 ^ ... ^ al-1 ^ al ^ ... ^ ar
prefix[l-1]   = a0 ^ a1 ^ ... ^ al-1
prefix[r] ^ prefix[l-1] = al ^ ... ^ ar      (duplicates cancel)

Any operation that is its own inverse can replace subtraction here — XOR is the classic one.

Common Mistakes

Using subtraction instead of XOR.

prefix[r] − prefix[l−1] computes nothing meaningful for XOR ranges.

Forgetting the l == 0 guard.

prefix[-1] crashes or wraps — handle queries starting at index 0 explicitly (or pad with a leading 0).

Complexity

OperationTime
BuildO(n)
QueryO(1)

My Private Notes

Notes are auto-saved locally to this device.