Why does a prefix-sum array break down when the underlying counters keep changing?
answer
- think about what a single write touches
- one counter moves — how many stored totals go stale?
- queries are cheap, writes are not
- the structure stores finished answers, not pieces
- O(log n) for both beats O(1) plus O(n)
basics
~20 sA prefix-sum array stores cumulative totals, so changing one counter invalidates every prefix after it — O(n) work per write. Fenwick and segment trees store partial aggregates instead, giving O(log n) for both updates and range queries.
solid answer
~50 sA prefix-sum array is a cache of finished answers: position `i` holds the total of everything up to `i`, so a range total is one subtraction, O(1). The price is that the cache is only valid for the data it was built from — bump one per-minute request counter and every prefix from that minute onward is stale, so a correct update costs O(n). On a live dashboard whose counters keep moving that flips the arithmetic: with `u` updates and `q` queries you pay O(n·u + q) instead of O((u + q) log n) with a Fenwick or segment tree, which store overlapping *partial* aggregates and touch only O(log n) of them per operation. The tree makes queries slightly slower — O(log n), not O(1) — and buys cheap writes. If writes are rare and arrive in batches, rebuilding the flat summary is still the right call; the read/write mix decides.
go deeper
Be ready to state the two costs out loud: O(1) range query but O(n) per single-value update for a prefix summary, versus O(log n) for both in a range-query tree. Knowing which side each structure optimises is the whole point.
Explain why the update is linear — every stored entry is a total that reaches back to the start, so one change invalidates all later entries. Then show the total-cost arithmetic for a given mix of queries and updates.
Demonstrate that you decide from the measured workload: batching or rare writes keep the flat summary, interleaved writes justify the tree. Spotting a full recomputation inside a hot write path in review is the practical skill here.
Own the framing that neither structure is better in the abstract — one buys read latency, the other buys write latency, and the update-to-query ratio is the input. Be ready to say what you would measure before letting a team add a tree to shared code.
## The structure that is really a cache of answers Given a series of n values — say a per-minute request counter for each of the last n minutes — a prefix summary stores at position `i` the total of positions 1..i. A range total over minutes `l..r` is then `P[r] - P[l-1]`: one subtraction, O(1), no matter how wide the window. That is as fast as range sums ever get, and it is why "just precompute the prefixes" is the first answer almost everyone gives. The catch is what a prefix summary *is*. Every entry is a finished answer that depends on all values before it. So when a single counter at minute `k` changes by some delta, entries `P[k]`, `P[k+1]`, …, `P[n]` are all wrong by that delta. Repairing them is a linear scan: **O(n) per single-value update**. There is no clever way around it — the structure has no notion of a partial, reusable piece; each entry commits to a total that reaches all the way back to the start. ## Where the cost actually lands Put numbers on the mix. With `q` range queries and `u` single-value updates over a series of length n: | approach | range query | single-value update | total for q queries + u updates | |---|---|---|---| | flat prefix summary | O(1) | O(n) | O(q + n·u) | | Fenwick tree | O(log n) | O(log n) | O((q + u) log n) | | segment tree | O(log n) | O(log n) | O((q + u) log n) | For a dashboard over a day of minute buckets, n is about 1,440 and the difference is invisible. For a year of minute buckets, n is over half a million: one update costs half a million touches instead of about twenty. If updates arrive at even a modest rate, the prefix summary is the bottleneck and the tree is not. Notice also what the tree gives up. Queries got **slower**, from O(1) to O(log n). A structure that supports cheap updates is not strictly better; it trades a constant-time read for a logarithmic one in exchange for turning a linear write into a logarithmic one. That trade is a win only when writes actually happen. ## Why partial aggregates fix it Both range-query trees are built on the same idea: instead of storing n final answers, store O(n) *overlapping partial* aggregates, each covering a contiguous block of the series, with block sizes arranged in powers of two. Then: - a query is assembled from O(log n) blocks that exactly tile the requested window; - an update touches only the O(log n) blocks whose span contains the changed position. No entry depends on the whole prefix, so no single change can invalidate a linear number of entries. A segment tree makes the blocks explicit as nodes of a binary tree over the index range; a Fenwick tree encodes the same block structure implicitly in the binary representation of the index, using about n words and a very tight loop. ## Reading the workload before choosing The decision rule an interviewer wants to hear is not "trees are better" but a question: **how often does the data change relative to how often it is read?** - **Immutable, or rebuilt wholesale on a schedule.** Keep the flat summary. Rebuilding it is O(n) once per batch, queries stay O(1), and the code is a single loop anyone can review. - **Interleaved single-value updates and range queries** — the live-counters case. Use a Fenwick or segment tree; the O(log n)/O(log n) profile is what the workload asks for. - **Writes vastly outnumber reads.** Consider storing the raw series and computing the rare range on demand in O(window). A structure you maintain on every write and query once a day is negative value. ## The failure mode to recognise in review The defect that shows up in real diffs is a prefix summary rebuilt inside the write path — a full recomputation each time a counter ticks. It is correct, it passes tests on small fixtures, and it is quadratic in the number of updates. The symptom is throughput that collapses as history grows, with a profile dominated by a loop that looks harmless. Recognising it is exactly the judgment this comparison is testing: the same range-sum requirement has two very different right answers, and which one you pick is decided by the update rate, not by the query.
- If range queries outnumber updates a thousand to one, would you still reach for a range-query tree?Probably not. With `q` queries and `u` updates the flat summary costs O(q + n·u) and the tree O((q + u) log n); when `u` is tiny the linear rebuilds are rare and the O(1) queries win on constants as well as code simplicity. The honest answer is to measure the real ratio and the real n rather than reasoning from asymptotics alone.
- Updates arrive in bursts of thousands, then the series is read all day. What changes?Batching removes the problem. Apply the whole burst to the raw series, then rebuild the flat summary once in O(n) and serve every read in O(1). You pay one linear pass per burst instead of one per update, and you keep the simplest possible structure — the tree only earns its complexity when updates and queries are genuinely interleaved.
- Does a range-query tree make queries faster than a prefix summary?No — it makes them slower, O(log n) instead of O(1). The tree's whole contribution is on the write side, turning an O(n) update into O(log n). Framing it as a strictly faster structure is the misread; it is a rebalancing of costs that only pays off when writes are frequent enough to dominate.
A prefix summary is a running bank-balance column: correcting one old transaction forces you to rewrite every balance below it. A range-query tree keeps subtotals per block instead, so one correction fixes only the handful of blocks that contain it.
saying these in an interview costs you the question
- Says prefix sums handle any range-sum workload
- Claims updating a prefix summary is O(1)
- Thinks a range-query tree makes queries faster than O(1)
- Ignores the update-to-query ratio when choosing
- Rebuilds the whole summary inside the write path