PrefixPrefix Techniques

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.

Learn Prefix XOR →
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