XOR of Numbers in a Given Range
Given two integers l and r, return the XOR of every integer from l to r inclusive, in constant time.
Intuition
This is not an algorithm you derive under pressure — it is a pattern you have to have seen. Write out the XOR of 1..n for the first ten values of n and the result depends only on n mod 4: it cycles through n, 1, n+1, 0. That gives XOR of 1..n in O(1). Extending it to an arbitrary range is the prefix trick you already know from prefix sums, except that XOR is its own inverse: f(r) ^ f(l-1) cancels everything below l because each shared value appears twice.
Approach
Solve the easier problem first: XOR of 1..n
Ignore l for a moment and just compute the XOR of 1 through n. The brute force is a one-line loop, O(n). To beat it, tabulate: n=1 gives 1, n=2 gives 3, n=3 gives 0, n=4 gives 4, n=5 gives 1, n=6 gives 7, n=7 gives 0, n=8 gives 8, n=9 gives 1. Group them in fours and the structure is obvious.
Read the pattern off the table
Every n with n % 4 == 1 gives 1 (n = 1, 5, 9, 13...). Every n with n % 4 == 2 gives n + 1 (n = 2 gives 3, n = 6 gives 7, n = 10 gives 11). Every n with n % 4 == 3 gives 0. And every multiple of 4 gives n itself (4, 8, 12). Four branches, no loop, O(1). Call this function f(n).
Turn the range into two prefixes
For the range l..r, note that f(r) is the XOR of 1..r, which is the XOR of 1..l-1 followed by the XOR of l..r. Since XOR undoes itself, XOR-ing f(r) with f(l-1) cancels the entire 1..l-1 portion — each of those values appears once in each operand and x ^ x = 0. What survives is exactly the XOR of l..r. So the answer is f(r) ^ f(l-1), two constant-time calls.
Solution & live demo
Edge cases
f(0) must return 0 — the XOR of an empty prefix. With 0 % 4 == 0 the multiple-of-4 branch returns 0, so the formula needs no special case.
The answer is that single number. f(r) ^ f(r-1) cancels everything below r and leaves r itself.
Nothing loops, so r can be as large as the integer type allows without any change in running time.