Prefix XOR: cancel a range | DSA & Design, Connected

Picture

Let prefix[i] XOR the values before i. A range left..right equals prefix[right+1] XOR prefix[left].

Predict

Which operation replaces subtraction for XOR prefixes?

Walk through the small example

XOR again. XOR is its own inverse, so two boundaries cancel their shared prefix.

Mental model and complete Python solution

Prefix sum removes the shared beginning with subtraction. Prefix XOR removes it by toggling the same bits a second time.

What the function promises: Build prefix XOR values and answer inclusive valid ranges.

def xor_prefix(values):
    prefix = [0]
    for value in values: prefix.append(prefix[-1] ^ value)
    return prefix

def range_xor(prefix, left, right):
    return prefix[right+1] ^ prefix[left]

prefix = xor_prefix([3,8,2,6])
assert range_xor(prefix,1,3) == (8^2^6)
assert range_xor(prefix,0,0) == 3

Work and storage: O(n) preprocessing, O(1) per query, O(n) storage.

When to recognize it: XOR is its own inverse, so two boundaries cancel their shared prefix.

Check before applying it: Do not mix arithmetic sum intuition with XOR; ordering and update contracts still matter.

Change one rule

Need maximum XOR of any pair.

See what changes

Use a bitwise trie that greedily seeks opposite bits while preserving available prefixes.

Connect

prefix sums: Both turn a range into two boundary summaries.

Fenwick tree: prefix sums with updates: Fenwick can use XOR for online point updates and prefix queries.