Prefix XOR and Prefix Product: Beyond Prefix Sum

Prefix sum is powerful, but the same logic applies to other associative operations: XOR, product, GCD, and more.

You've mastered cumulative sums. Now imagine applying the same preprocessing technique to XOR operations (for bit manipulation) or products (for array multiplication). The pattern is identical—only the operation changes.

This guide will teach you prefix XOR, prefix product, when to use each variant, and how to avoid the pitfalls unique to non-additive operations.

TL;DR

Use prefix XOR when:

• Need XOR of subarrays
• Bit manipulation problems
• Finding pairs with target XOR

Use prefix product when:

• Product of array except self
• Subarray product queries
• Need to avoid division

Key differences from prefix sum:

• XOR: Identity is 0, self-inverse property (a ^ a = 0)
• Product: Identity is 1, division by zero issues

Templates:

Prefix XOR:

prefix_xor = [0]
for num in nums:
    prefix_xor.append(prefix_xor[-1] ^ num)

# Query XOR from i to j
xor_range = prefix_xor[j+1] ^ prefix_xor[i]

Prefix Product:

# Forward pass
prefix = 1
for i in range(n):
    result[i] = prefix
    prefix *= nums[i]

# Backward pass
suffix = 1
for i in range(n-1, -1, -1):
    result[i] *= suffix
    suffix *= nums[i]

Prefix XOR

What Is Prefix XOR?

Apply prefix sum logic to XOR operations.

Definition: prefix_xor[i] = XOR of all elements from index 0 to i-1

Formula:

xor(i, j) = prefix_xor[j+1] ^ prefix_xor[i]

Why It Works

XOR properties:

1. Associative: (a ^ b) ^ c = a ^ (b ^ c)
2. Self-inverse: a ^ a = 0
3. Identity: a ^ 0 = a

Proof:

prefix_xor[j+1] = nums[0] ^ nums[1] ^ ... ^ nums[j]
prefix_xor[i] = nums[0] ^ nums[1] ^ ... ^ nums[i-1]

prefix_xor[j+1] ^ prefix_xor[i]
= (nums[0] ^ ... ^ nums[j]) ^ (nums[0] ^ ... ^ nums[i-1])
= nums[i] ^ nums[i+1] ^ ... ^ nums[j]  (first i elements cancel out)

The Template

def xor_queries(arr: List[int], queries: List[List[int]]) -> List[int]:
    """
    LeetCode #1310: XOR Queries of a Subarray
    Time: O(n + q), Space: O(n)
    """
    # Build prefix XOR
    prefix_xor = [0]
    for num in arr:
        prefix_xor.append(prefix_xor[-1] ^ num)
    
    # Answer queries
    result = []
    for left, right in queries:
        xor_val = prefix_xor[right + 1] ^ prefix_xor[left]
        result.append(xor_val)
    
    return result

# Test
arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3], [3, 3]]
print(xor_queries(arr, queries))
# [2, 7, 14, 8]

Example Walkthrough

arr = [1, 3, 4, 8]

Build prefix XOR:
prefix_xor[0] = 0
prefix_xor[1] = 0 ^ 1 = 1
prefix_xor[2] = 1 ^ 3 = 2
prefix_xor[3] = 2 ^ 4 = 6
prefix_xor[4] = 6 ^ 8 = 14

prefix_xor = [0, 1, 2, 6, 14]

Query [0, 1]: XOR of arr[0..1] = 1 ^ 3
= prefix_xor[2] ^ prefix_xor[0]
= 2 ^ 0 = 2 ✓

Query [1, 2]: XOR of arr[1..2] = 3 ^ 4
= prefix_xor[3] ^ prefix_xor[1]
= 6 ^ 1 = 7 ✓

When to Use Prefix XOR

Use when:

• Finding XOR of subarrays
• Bit manipulation problems
• Pairs with target XOR
• Counting subarrays with XOR = k

Example problems:

• XOR Queries of a Subarray (#1310)
• Count Triplets That Can Form Two Arrays of Equal XOR (#1442)
• Maximum XOR of Two Numbers in an Array (#421)

Prefix Product

What Is Prefix Product?

Apply prefix sum logic to multiplication.

Challenge: Division by zero breaks the simple formula.

Solution: Use prefix and suffix products without division.

The Template

def productExceptSelf(nums: List[int]) -> List[int]:
    """
    LeetCode #238: Product of Array Except Self
    Time: O(n), Space: O(1) excluding output
    """
    n = len(nums)
    result = [1] * n
    
    # Build prefix products (left to right)
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Build suffix products (right to left) and multiply
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

# Test
print(productExceptSelf([1, 2, 3, 4]))
# [24, 12, 8, 6]

Example Walkthrough

nums = [1, 2, 3, 4]

Step 1: Build prefix products (left to right)
i=0: result[0] = 1 (no elements to the left), prefix = 1*1 = 1
i=1: result[1] = 1 (product of [1]), prefix = 1*2 = 2
i=2: result[2] = 2 (product of [1,2]), prefix = 2*3 = 6
i=3: result[3] = 6 (product of [1,2,3]), prefix = 6*4 = 24

result = [1, 1, 2, 6]

Step 2: Build suffix products (right to left)
i=3: result[3] *= 1 = 6*1 = 6, suffix = 1*4 = 4
i=2: result[2] *= 4 = 2*4 = 8, suffix = 4*3 = 12
i=1: result[1] *= 12 = 1*12 = 12, suffix = 12*2 = 24
i=0: result[0] *= 24 = 1*24 = 24, suffix = 24*1 = 24

result = [24, 12, 8, 6] ✓

Verify:
result[0] = 2*3*4 = 24 ✓
result[1] = 1*3*4 = 12 ✓
result[2] = 1*2*4 = 8 ✓
result[3] = 1*2*3 = 6 ✓

Handling Zeros

Problem: If the array contains zeros, naive product approaches fail.

Solution: The prefix/suffix approach handles zeros naturally.

Example:

nums = [1, 2, 0, 4]

Prefix pass:
result = [1, 1, 2, 0]

Suffix pass:
result = [0, 0, 8, 0]

Verify:
result[0] = 2*0*4 = 0 ✓
result[1] = 1*0*4 = 0 ✓
result[2] = 1*2*4 = 8 ✓
result[3] = 1*2*0 = 0 ✓

See detailed guide: Prefix Product Pitfalls

When to Use Prefix Product

Use when:

• Product of array except self
• Can't use division
• Need O(1) extra space

Don't use when:

• Can use division (simpler)
• Array has many zeros (consider counting zeros)

Prefix GCD/LCM

Extending to Other Operations

The prefix pattern works for any associative operation.

GCD (Greatest Common Divisor):

def prefix_gcd(arr):
    prefix = [0]
    for num in arr:
        prefix.append(gcd(prefix[-1], num))
    return prefix

# Query GCD of range [i, j]
gcd_range = gcd(prefix[j+1], prefix[i])  # Wait, this doesn't work!

Problem: GCD doesn't have the inverse property like XOR.

Solution: For GCD/LCM, you need segment trees or sparse tables for efficient range queries.

When Prefix Pattern Doesn't Apply

Doesn't work for:

• Max/Min: No inverse operation
• GCD/LCM: No inverse operation
• Non-associative operations

Use instead:

• Segment Tree
• Sparse Table
• Other data structures

Comparison: Sum vs XOR vs Product

Common Mistakes

Mistake 1: Forgetting Identity Elements

❌ Wrong:

# XOR: Starting with 1 instead of 0
prefix_xor = [1]  # Should be [0]

# Product: Starting with 0 instead of 1
prefix_product = 0  # Should be 1

✅ Correct:

# XOR identity is 0
prefix_xor = [0]

# Product identity is 1
prefix_product = 1

Mistake 2: Using Division with Zeros

❌ Wrong:

# Naive product except self with division
total_product = 1
for num in nums:
    total_product *= num

result = [total_product // num for num in nums]
# Fails if any num is 0!

✅ Correct:

# Use prefix/suffix approach (no division)
# See template above

Mistake 3: Misunderstanding XOR Properties

❌ Wrong:

# Thinking XOR is like addition
xor_range = prefix_xor[j+1] - prefix_xor[i]  # Wrong operator!

✅ Correct:

# XOR is its own inverse
xor_range = prefix_xor[j+1] ^ prefix_xor[i]

Practice Problems

Prefix XOR

1. XOR Queries of a Subarray (#1310) - Direct template
2. Count Triplets That Can Form Two Arrays of Equal XOR (#1442) - XOR + hash map
3. Maximum XOR of Two Numbers in an Array (#421) - Trie + XOR

Prefix Product

1. Product of Array Except Self (#238) - Classic problem
2. Maximum Product Subarray (#152) - DP variant
3. Sign of the Product of an Array (#1822) - Count negatives

Advanced

1. Subarray With Elements Greater Than Varying Threshold (#2334) - Prefix min
2. Range GCD Queries - Sparse table needed

FAQ

Q: Can I use prefix sum logic for any operation?

A: Only for associative operations. The operation must satisfy (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c).

Q: Why doesn't prefix GCD work like prefix XOR?

A: GCD doesn't have an inverse operation. gcd(a, b) can't be "undone" to recover a or b.

Q: When should I use prefix product vs just calculating products?

A: Use prefix/suffix when you can't use division (e.g., problem forbids it, or array has zeros).

Q: Can I combine prefix sum with prefix XOR?

A: Yes! Some problems need both. For example, finding subarrays with both sum and XOR conditions.

Q: What's the identity element for an operation?

A: The value that doesn't change the result:

• Addition: 0 (a + 0 = a)
• Multiplication: 1 (a * 1 = a)
• XOR: 0 (a ^ 0 = a)
• Max: -∞
• Min: +∞

Conclusion

The prefix pattern extends beyond sums to any associative operation.

Key principles:

• XOR: Self-inverse property, identity is 0
• Product: Use prefix/suffix to avoid division
• Associative operations enable the pattern
• Identity elements matter for initialization

The templates:

Prefix XOR:

prefix_xor = [0]
for num in nums:
    prefix_xor.append(prefix_xor[-1] ^ num)

xor_range = prefix_xor[j+1] ^ prefix_xor[i]

Prefix Product:

# Prefix pass
for i in range(n):
    result[i] = prefix
    prefix *= nums[i]

# Suffix pass
for i in range(n-1, -1, -1):
    result[i] *= suffix
    suffix *= nums[i]

When to use:

• XOR: Bit manipulation, subarray XOR queries
• Product: Array product except self, no division allowed

Master these variants, and you'll recognize prefix patterns in unexpected places. For more, see the complete prefix sum guide, prefix product pitfalls, and 1D template.

Next time you see XOR or product operations, think: Can I apply the prefix pattern?