PrefixAlgorithmaka cumulative XOR, XOR prefix array, range XOR

Prefix XOR

Precompute X[i] = a[0] ^ … ^ a[i-1] so any range XOR a[l..r] is X[r+1] ^ X[l] — XOR is its own inverse, so no subtraction is needed.

▶ VisualizePattern: Prefix SumPractice (2)
Progress

Overview

Prefix XOR is Prefix Sum with ^ in place of +. Because every value is its own inverse under XOR (x ^ x = 0), the "subtract the earlier prefix" step is also an XOR: xor(l, r) = X[r+1] ^ X[l]. Building X costs O(n); each range XOR query costs O(1).

The technique combines naturally with a Hash Map to count subarrays whose XOR equals a target (X[r+1] ^ X[l] = k ⇔ X[l] = X[r+1] ^ k) and with a Trie of bit strings to find the subarray with maximum XOR. It also underlies puzzles like "find the missing number" and "single number" where XOR cancels pairs.

xorbitwiserange queryO(1) queryself-inverse

Intuition

A mental model before the formal terms.

A light switch flipped an even number of times is back where it started. XOR-ing a sequence of numbers is flipping a row of switches, one row per bit. To learn what the switches did between positions l and r, take the state after r, then replay the flips from before l — since replaying a flip undoes it, that is just XOR-ing with the earlier state.

How it works

  1. Allocate X of length n + 1 with X[0] = 0.
  2. For i from 1 to n: X[i] = X[i-1] ^ a[i-1].
  3. Range query xor(l, r): return X[r+1] ^ X[l].
  4. Count subarrays with XOR k: scan with running X; maintain seen[value] seeded with seen[0] = 1; add seen[X ^ k] to the count at each step, then seen[X] += 1.
  5. Maximum subarray XOR: insert each prefix into a binary Trie; for the current prefix greedily walk the trie choosing the opposite bit at each level to maximize the result.

Why it works

Cancellation: X[r+1] ^ X[l] = (a[0] ^ … ^ a[r]) ^ (a[0] ^ … ^ a[l-1]). XOR is associative and commutative, so the terms pair up: every a[i] with i < l appears twice and vanishes (a[i] ^ a[i] = 0), leaving a[l] ^ … ^ a[r].

Counting: a subarray a[l..r] has XOR k iff X[r+1] ^ X[l] = k, and XOR-ing both sides by X[r+1] gives X[l] = X[r+1] ^ k. Every earlier prefix equal to that value is a valid left endpoint, so a hash-map lookup counts them in O(1).

The argument is identical to prefix sums; the only difference is that the inverse operation is XOR itself rather than subtraction, which removes any overflow concerns and makes the prefix array fit in the same bit width as the input.

Recognition

How to tell a problem wants this.

  • "XOR of all elements between `l` and `r`", "range XOR queries", "XOR queries of a subarray".
  • "Number of subarrays whose XOR equals k", "count pairs (i, j) with a[i] ^ … ^ a[j] = 0".
  • "Maximum XOR of any subarray" or "maximum XOR of two numbers" — prefix XOR plus a binary trie.
  • "Find the missing number in 0..n", "every element appears twice except one" — XOR cancellation without a prefix array.
  • Constraints stating values < 2^20 or < 2^31: a hint that bitwise structure (trie depth, mask size) matters.
“sum of subarray” → Prefix Sum“parity/odd occurrences” → Bit Manipulation

Interactive visualization

Play, step, change the input. ← → and space work too.

a
5
0
3
1
8
2
6
3
2
4
7
5
4
6
X (prefix xor)
0
0
1/11XOR behaves like addition where every element is its own inverse (x ^ x = 0). So a prefix XOR array answers range XOR just like prefix sums answer range sums. X[0] = 0.
Being XORed inQueried rangePrefix entries usedAnswer
PseudocodeLearn Prefix XOR →
1X[0] = 0
2for i in 0 .. n-1: X[i+1] = X[i] ^ a[i]
3query(l, r) = X[r+1] ^ X[l]
Variables
n7
Complexity
best O(n)
avg O(n + q)
worst O(n + q)
space O(n)
Speed

Pseudocode

1X = array of n + 1 zeros
2for i in 1..n: X[i] = X[i-1] ^ a[i-1]
3range_xor(l, r) = X[r+1] ^ X[l]
4# count subarrays with XOR k
5seen = {0: 1}, run = 0, count = 0
6for x in a:
7  run ^= x
8  count += seen[run ^ k]
9  seen[run] += 1
10return count

Implementations

1# XOR Queries of a Subarray: answer each [l, r] with a[l] ^ ... ^ a[r]
2def xor_queries(a: list[int], queries: list[list[int]]) -> list[int]:
31 · Prefix XOR array with sentinel X[0] = 0
4    x = [0] * (len(a) + 1)
5    for i, v in enumerate(a):
6        x[i + 1] = x[i] ^ v
72 · A range XOR is two lookups: X[r+1] ^ X[l] (XOR is its own inverse)
8    return [x[r + 1] ^ x[l] for l, r in queries]
9 
10 
11# Count subarrays whose XOR equals k
12def count_subarrays_with_xor(a: list[int], k: int) -> int:
133 · Running prefix XOR with occurrence counts; seed the empty prefix
14    seen = {0: 1}
15    run = 0
16    count = 0
17    for v in a:
18        run ^= v
194 · Earlier prefixes equal to run ^ k close a subarray with XOR k
20        count += seen.get(run ^ k, 0)
215 · Record this prefix for later right endpoints
22        seen[run] = seen.get(run, 0) + 1
23    return count
Walkthrough
  1. enumerate(a) yields (i, v) pairs, filling x[i + 1] = x[i] ^ v without manual index arithmetic.
  2. The list comprehension answers all queries in one expression — each is two list reads and one ^.
  3. Python ints are arbitrary precision, so ^ works on values of any width with no truncation, unlike JS int32 coercion.
  4. A plain dict with seen.get(run ^ k, 0) reads without inserting — the defaultdict alternative would grow on every miss.
  5. seen[run] = seen.get(run, 0) + 1 records the prefix after the lookup, keeping k == 0 correct.
Complexity (this implementation)
time O(n + q) · space O(n)

Arbitrary-precision ints: XOR on huge values costs O(bits), still effectively O(1) for 32/64-bit inputs.

Language notes
  • itertools.accumulate(a, operator.xor, initial=0) builds the prefix XOR array in one call (Python 3.8+).
  • ^ on negative ints follows two's-complement semantics over infinite sign extension — well defined, but surprising if you expect fixed-width bits.
  • functools.reduce(operator.xor, a, 0) is the one-shot XOR of a whole list (Single Number in one line).
Common mistakes in this language
  • Using defaultdict(int) and reading seen[run ^ k] — correct counts, but every miss inserts a zero entry and grows the dict.
  • Writing x[r] ^ x[l] (excludes a[r]) or seeding x without the leading 0.
  • Confusing ^ (XOR) with ** (power) — a classic slip for newcomers from math notation.
Language differences that matter here
  • Value width: JS/TS bitwise ops truncate to signed 32 bits (values >= 2^32 silently lose high bits; use BigInt beyond); C++ int XOR is well defined and cannot overflow; Python ints XOR at any width.
  • Sign surprises: JS int32 XOR can yield negative numbers when bit 31 is set (>>> 0 reinterprets as unsigned); Python treats negatives as infinitely sign-extended two's complement.
  • No widening needed anywhere — unlike prefix *sums*, the prefix XOR array fits the input type in every language (no long long, no BigInt for 32-bit inputs).
  • Stdlib builds: Python accumulate(a, operator.xor, initial=0); C++ std::partial_sum with std::bit_xor<int>(); JS/TS need the manual loop.
  • Lookup semantics in the counting variant: C++ unordered_map::operator[] and Python defaultdict insert on read (use find / dict.get); JS/TS Map.get never inserts.

Complexity

Best
O(n)
Average
O(n + q)
Worst
O(n + q)
Space
O(n)

O(n) build, O(1) per query. Maximum-XOR-subarray with a trie is O(n · B) for B-bit values.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Range XOR queries on a static array.
  • Counting or finding subarrays with a given XOR.
  • Maximum subarray XOR (with a binary trie over prefixes).
  • Any cumulative computation whose operation is XOR — parity tracking, toggling state.
Avoid it when
  • The array is updated between queries — a Fenwick Tree supports XOR point updates and range queries in O(log n).
  • The question is about sums, counts, or ordering — XOR carries no magnitude information; use Prefix Sum.
  • Range AND / OR queries — those operations are not invertible; use a Sparse Table (idempotent) or Segment Tree.

Alternatives

Prefix SumFenwick TreeSegment TreeXOR Patterns

Common mistakes

  • Writing X[r] ^ X[l] and excluding a[r], or X[r+1] ^ X[l+1] and excluding a[l].
  • Trying to "subtract" with − out of habit; the inverse of XOR is XOR.
  • Forgetting seen[0] = 1 in the counting variant (misses subarrays starting at index 0).
  • Assuming XOR-prefix tricks extend to AND or OR — they do not, because those operations lose information.

Interview patterns

  • XOR Queries of a Subarray — direct application.
  • Count Triplets That Can Form Two Arrays of Equal XOR: count (i, k) with X[i] == X[k+1], contributing k − i triplets.
  • Maximum XOR of Two Numbers in an Array / maximum subarray XOR with a bitwise trie.
  • Single Number and Missing Number via cancellation.
  • Decode XORed Array: reconstruct a from encoded[i] = a[i] ^ a[i+1] — a prefix XOR in disguise.
Interview questions on this
Mock interviews

Example problems

Single NumbereasyRange XOR Queries with Updatesmedium