Everything you've built so far — prefix sums, difference arrays, 2D prefix tables — relies on addition. And addition has a very convenient property: you can undo it. If prefix[j] = 14 and prefix[i] = 8, you subtract to get 6. The subtraction perfectly reverses the addition, recovering the exact range sum.

But what if you need the XOR of a range? That shows up in problems involving bit manipulation, cryptographic checksums, and parity queries. What about the product of a range? That appears in combinatorics and probability calculations.

And here's the really interesting case: what about the maximum of a range? Range-max queries are everywhere — stock price windows, signal processing, sliding-window problems. Can you build a “prefix max” array and answer range-max queries in O(1) the same way you answer range-sum queries?

Imagine you confidently build prefix_max = [3, 5, 5, 7, 7, 9] from the array [3, 5, 2, 7, 1, 9]. You need the max of indices 2 through 4. You try prefix_max[5] - prefix_max[2] = 9 - 5 = 4. But the actual max of [2, 7, 1] is 7. What went wrong?

Subtraction doesn't “undo” max the way it undoes addition. When you subtract two prefix sums, you recover the exact range total because addition is perfectly reversible. But max(3, 5, 2, 7, 1, 9) - max(3, 5) gives you 9 - 5 = 4 — a number that has nothing to do with the maximum of the remaining elements. The max operation destroys information about individual values. Once you know the running maximum is 7, you've lost track of whether the elements were [2, 7, 1] or [7, 7, 7] or [0, 7, 0].

This failure tells you something deep. Before we get to the rule, let's test it experimentally across multiple operations.

Some of these operations work with the prefix trick. Some don't. The question is: how do you tell?

Test three operations — addition, XOR, and max — with the prefix technique. Build the prefix array, then try to recover a range answer.

Two of them work. One of them fails. Your job: figure out why.

You just discovered the fundamental theorem of prefix computation. It's not about addition. It's not about arrays. It's about one question:

Can you undo the operation?

If combining two values with an operation is a one-way street — if information is permanently lost — then you can't reverse the accumulation, and the prefix trick collapses. If the operation has an inverse, you can “subtract” the unwanted prefix and recover the exact range answer. Let's go operation by operation.

Addition works because subtraction exists. prefix[r+1] - prefix[l] peels away the first l elements and leaves exactly arr[l] + ... + arr[r]. The identity element is 0 (adding zero changes nothing), and every number has an additive inverse. This is the textbook case.

XOR works — and the reason is elegant. XOR is its own inverse: a ^ a = 0 for any a. That means prefix[r+1] ^ prefix[l] cancels out the unwanted prefix using the same operation. You don't need a separate “subtraction” — XOR is its own subtraction. At the bit level, each bit position is independent: 1 ^ 1 = 0, 0 ^ 0 = 0. Applying XOR twice always returns to the original value. The identity element is 0 (XOR with zero changes nothing).

This is why XOR appears so often in competitive programming. It has all the algebraic properties of addition (commutative, associative, has an identity, has an inverse) but operates on bits instead of magnitudes. Prefix XOR arrays let you answer “what's the XOR of this range?” in O(1), which is the key to problems like “find the missing number,” “find the unique element,” and “maximum XOR subarray.”

Multiplication almost works. Division is the inverse, the identity is 1, and prefix[r+1] / prefix[l] would give you the product of the range — if no element is zero. A single zero in the array makes prefix[i] = 0 for all subsequent positions, and you can't divide by zero to recover. So prefix products work under the constraint that no element is zero (or you handle zeros as special cases with extra bookkeeping).

Max fails completely. Here's why: max(3, 7, 2, 9) is 9. But knowing the maximum is 9 doesn't tell you what the other numbers were. Was the second-largest 8? 3? 0? You have no idea. The max operation destroys information — it collapses many possible inputs into the same output. There is no “un-max” that recovers the original values. Without an inverse, prefix_max[r+1] (un-max) prefix_max[l] is meaningless.

GCD fails for the same reason. gcd(12, 8) = 4, but knowing the GCD is 4 doesn't tell you the original numbers. Was it gcd(12, 8) or gcd(4, 4) or gcd(100, 4)? The information is gone.

So here's your decision framework. When you encounter a new range-query problem, ask three questions in order:

1. Is the operation associative? (Can you build a prefix array at all?) Addition, XOR, multiplication, max, GCD — all associative. This is rarely the bottleneck.
2. Does the operation have an inverse? (Can you "subtract" the prefix?) Addition has subtraction. XOR has itself. Multiplication has division (with caveats). Max has nothing. This is the gate.
3. Are there degenerate elements? (Does zero break multiplication? Does the identity cause edge cases?) These are the implementation traps.

If the answer to question 2 is “no,” the prefix trick won't work, and you need a different data structure entirely. For range-max queries, that's a sparse table (O(n log n) precomputation, O(1) query) or a segment tree (O(n) build, O(log n) query). For range-GCD, it's a segment tree. The prefix trick is powerful, but invertibility is its hard boundary.

That's the generalization worth carrying out of this module: the pattern isn't “prefix sums.” The pattern is “precompute cumulative values, then recover ranges by inverting.” Addition just happens to be the most common instance.