Why can a Fenwick tree answer arbitrary range sums but not arbitrary range minima?
answer
- how does a prefix-based structure build a general range?
- one structure subtracts, the other combines
- what property does subtraction demand?
- can you undo a minimum?
- monoid is enough to combine; a group is needed to remove
basics
~20 sA Fenwick tree answers a general range by subtracting prefixes, which requires an invertible aggregate. Minimum has no inverse — two prefix minima say nothing about the range between them — so range minima need a structure that combines covering blocks.
solid answer
~50 sA Fenwick tree natively stores prefixes, so it answers a range `l..r` as `prefix(r)` minus `prefix(l-1)`. That subtraction is the whole trick, and it demands an **invertible** operation — a group, not just an associative one. Minimum is associative, commutative and idempotent, but it has no inverse: if the coldest sensor reading in the first hour was −40 and the coldest in the first ten minutes was also −40, nothing tells you the coldest reading in the remaining fifty minutes. The information was destroyed when the two prefixes collapsed. A segment tree never subtracts; it combines the O(log n) canonical nodes that exactly tile `l..r`, so it needs only associativity and an identity — +∞ for minimum. That is why a mutable "coldest reading in any requested window" service wants a segment tree, while a mutable range-sum counter can use either.
go deeper
Remember the split: prefix-subtraction structures serve sums and counts, while range minimum or maximum over a changing series needs a segment tree. Knowing which question each structure can answer is the takeaway.
Explain the mechanism — a general range comes from subtracting one prefix from another, and subtraction demands an inverse. Show with a concrete example why two prefix minima cannot reconstruct the minimum in between.
Demonstrate the diagnostic instinct: the bug ships as correct answers on windows starting at the beginning and wrong ones elsewhere. Say how you would catch it — randomised comparison against a brute-force scan, not hand-picked cases.
Own the rule that the aggregate's algebra picks the structure, not convenience. Be ready to argue why encoding a monotone-updates-only invariant across a service is usually a worse bargain than paying for the more general structure.
## Two different ways to assemble an answer Both range-query structures store partial aggregates over power-of-two-sized blocks, but they assemble a range from them in fundamentally different ways. - A **segment tree** finds the O(log n) blocks that exactly tile `[l, r]` and combines them. It only ever *adds information together*. - A **Fenwick tree** answers prefixes only. A general range comes from `prefix(r) ⊖ prefix(l-1)` — it *removes* the unwanted head from a longer answer. That difference is the entire story. Combining needs the operation to be **associative** with an **identity** (a monoid). Removing additionally needs an **inverse** for every value (a group). ## Why minimum has no inverse Take a sensor time-series of temperature readings, one per minute, and ask for the coldest reading in a requested window. Suppose the coldest reading over minutes 1–60 is −40, and the coldest over minutes 1–10 is also −40. What is the coldest over minutes 11–60? It could be −40 (the −40 recurred later), or −5, or anything ≥ −40. The prefix minimum is a lossy summary: it remembers the winner and forgets the field. There is no operation `⊖` such that `min(1..r) ⊖ min(1..l-1) = min(l..r)`, because the left-hand side simply does not contain enough information. Sum is different. `sum(1..r) − sum(1..l-1)` works because addition has an inverse: every contribution can be individually withdrawn. Counts, XOR (its own inverse) and any total over an invertible aggregate behave the same way. Products *almost* qualify and then betray you on a zero factor, which is exactly the kind of edge case that ships as a division-by-zero at 3am. Notice that idempotence is a red herring here: `min(x, x) = x` is a lovely property and buys nothing for subtraction. Neither does commutativity. The one property that matters for the prefix-subtraction trick is invertibility, and minimum lacks it. ## What that means in practice For a mutable series where the query is "coldest reading in window `[l, r]`" and individual readings get corrected or backfilled: - **Segment tree over minimum.** Node value = the minimum of its block, parent = `min(left, right)`, identity = +∞ for the disjoint case. Query O(log n), point update O(log n). This is the straightforward answer. - **Flat prefix-minimum summary.** Fails for the same reason the Fenwick tree does, and additionally cannot absorb updates cheaply. It is not a shortcut around the problem; it is the same lossiness in a simpler wrapper. - **Fenwick tree, restricted.** There is a well-known variant that supports *prefix* minima when updates only ever lower a value — never raise one. It is genuinely useful in narrow settings, and it is worth naming to show you know the boundary, but it does not answer arbitrary ranges and it breaks the moment a correction increases a reading. Do not offer it as a general solution. ## The general rule worth carrying away Before choosing between these structures, classify your aggregate: | aggregate | associative | invertible | prefix-subtraction works | segment tree works | |---|---|---|---|---| | sum, count | yes | yes | yes | yes | | XOR | yes | yes | yes | yes | | minimum, maximum | yes | no | no | yes | | gcd | yes | no | no | yes | | mean | not on the value alone | — | no | yes, if you store total and count | The left column decides the structure, not the other way round. A candidate who reaches for the compact prefix-based structure first and only then asks what the operation is has the reasoning backwards — and the failure is not a performance regression, it is wrong answers. ## How this shows up as a bug rather than a design question The realistic version of this mistake is incremental. A service starts with mutable range sums over per-minute counters and uses the compact prefix structure, correctly. Months later someone adds a "coldest reading in the window" panel, sees an existing range-query structure sitting right there, and extends it by storing minima in the same nodes and subtracting prefixes. The code compiles, the tests on windows that start at the beginning of the series pass (because those are pure prefixes, where the structure genuinely is correct), and every window with a non-trivial left endpoint is quietly wrong. The lesson to state in an interview: the structure's contract is not "range queries", it is "range queries over an invertible aggregate", and the two failures look identical in a code review that is not asking about algebra.
- Which properties does a segment tree actually require of its combine, then?Associativity, plus an identity for the disjoint case. Associativity matters because the query is free to combine the covering blocks in whatever order the recursion returns them, and the grouping must not change the answer. Commutativity is not required — order-sensitive combines like matrix product work fine as long as blocks are combined left to right — and no inverse is needed at all.
- Someone proposes a prefix-minimum structure that supports lowering a value but not raising it. Is that sound?For prefix minima only, and only under monotone updates, yes — the restricted variant exists and is used. But it answers prefixes, not arbitrary ranges, and a single correction that raises a reading invalidates stored minima it can no longer repair. Accepting it means encoding "values only ever decrease" as an invariant the whole service must uphold, which is usually a worse bargain than a segment tree.
- How would you catch this class of mistake in review or in tests?Test windows with non-trivial left endpoints, not just prefixes — a prefix-subtraction structure is genuinely correct on any window starting at position 1, which is why hand-picked tests pass. The durable fix is a randomised comparison against a brute-force scan over random operation sequences, which finds a broken aggregate on the first mismatched window.
Prefix sums are like a bank balance — you can always subtract an earlier balance to recover what happened in between. Prefix minima are like a record low temperature: knowing the record for the year and for January tells you nothing about February.
saying these in an interview costs you the question
- Says a prefix-based structure handles minimum like sum
- Thinks storing prefix minima solves range minimum
- Confuses associativity with invertibility
- Cites idempotence or commutativity as the key property
- Tests only windows that start at the first position