When does maintaining a prefix-sum array cost more than scanning the range each time?
answer
- Derived data is a cache
- Count reads against writes
- One edit poisons every later total
- Appending is cheap, editing is not
- u·n + q versus u + q·n
basics
~20 sWhen the underlying values change. A point edit invalidates every cumulative total after it, forcing an O(n) rebuild, so an edit-heavy workload pays O(n) per write to save O(n) per read — and with few queries, the O(n) build never amortizes at all.
solid answer
~50 sTwo situations. First, too few queries: the build is itself an O(n) pass, so answering one or two ranges costs about the same as scanning them, plus O(n) memory you did not need. Second, and more important in production: mutation. Every cumulative total after an edited position becomes wrong, so a point update means an O(n) fix-up. With u updates and q queries the precomputed path costs roughly O(u·n + q) against O(u + q·n) for scanning — precompute wins only while queries dominate writes. Note the asymmetry that trips people: *appending* a new value is O(1), since it only extends the array, while editing an existing one is O(n). So an append-only spend ledger with heavy reporting is an ideal fit, and the same ledger once late refunds start rewriting past days is not. When both reads and writes are hot you need a structure with logarithmic update and query instead.
go deeper
Recognise that building the array is itself a full pass, so for a single range question you should just add the values up. Knowing the build is not free is the point here.
Compare the two totals explicitly — roughly u·n + q against u + q·n — and conclude that precomputation wins only while queries dominate updates. Be able to explain why one edit invalidates a whole suffix.
Bring the append-versus-edit asymmetry and the operational consequences: rebuild latency proportional to dataset size on the write path, memory duplication, and the fact that one bad source value corrupts every later total rather than one reading.
Own the staleness contract and the migration. Decide whether derived totals are rebuilt synchronously, swapped in from a side build, or refreshed on a schedule with a published lag — and when the workload has shifted enough that a more complex structure is worth its maintenance cost.
## Framing it as a cost model, not a rule A prefix array is a cache of derived data. Like any cache it is a bet: pay once up front, win on every read, lose whenever the source changes. Deciding whether to build one is arithmetic over the workload, not a pattern-matching reflex on the word "range". Let n be the number of values, q the number of range queries, u the number of updates. | Strategy | Per query | Per point update | Total | |---|---|---|---| | Scan the range | O(range width), up to O(n) | O(1) | O(u + q·n) | | Prefix array, rebuilt on write | O(1) | O(n) | O(u·n + q) | The two totals cross where u·n and q·n balance — that is, roughly where updates and queries occur equally often. Read-dominated: precompute. Write-dominated: do not. Balanced and both hot: neither of these is the right structure, and the answer is a range structure with logarithmic update *and* query, which is a different tool entirely. ## The one-query case If the range is asked once, building the array is strictly worse: the build is a full pass, the scan is at most a full pass, and the build additionally allocates O(n). This sounds too obvious to state, yet it is the most common real-world misuse — a candidate who has drilled the pattern builds the array reflexively in a function that gets called once. The interviewer is usually probing exactly this reflex. ## The asymmetry that decides real designs Updates are not one thing. - **Append** a new value at the end: O(1) amortized. Nothing already stored becomes wrong, because a cumulative total only depends on values before it. Extend the array by one entry equal to the last total plus the new value. - **Edit** an existing value at position i: every entry from i+1 to n shifts by the delta, so O(n - i), which is O(n) in the worst case. You can apply the delta rather than recomputing from scratch, but it is still a linear sweep. - **Insert or delete** in the middle: O(n) as well, and the index mapping for every stored query changes too. That asymmetry maps directly onto real systems. An append-only event ledger with a reporting layer on top is a textbook fit: the derived totals only ever grow at the tail. The same ledger with late corrections — a refund posted against a day three weeks ago — is not, because each correction rewrites a suffix. When a design that started append-only starts accepting back-dated edits, this is the structure that quietly becomes the bottleneck, and the symptom is write latency climbing with dataset size rather than with traffic. ## What the asymptotics understate Constants matter more here than usual, in both directions. A prefix build is a single sequential pass with perfect locality and a trivially predictable access pattern — one of the fastest things hardware does. So the crossover in practice sits further toward "rebuild anyway" than the model suggests, especially for moderate n where the whole array fits in cache. Conversely, the memory cost is real: the array is the same length as the data with wider accumulators, and for a large dataset that doubling may be the binding constraint long before time is. ## Operational considerations beyond the loop - **Staleness.** If you rebuild periodically rather than per write, you have chosen an eventual-consistency window for your reports. That is a legitimate design, but it must be a stated one, with the window in the contract. - **Blast radius.** A single wrong value in the source corrupts every later total, so an error is not localised the way it is with on-demand scanning. Add a cheap invariant check — the last cumulative entry against an independently computed total. - **Rebuild cost against availability.** For a large dataset, a synchronous full rebuild on the write path is a latency spike proportional to n. Rebuilding off to the side and swapping the reference is the usual fix, at the cost of holding two copies briefly. ## How to answer it in an interview Do not answer "when there are updates". Give the model — one query means scan; many queries over static data means precompute; frequent point edits mean the O(n) rebuild dominates and you need a different structure — then name the append-versus-edit asymmetry, because that is the distinction that shows you have run this in production rather than only solved it on paper.
- Why is appending a new value cheap when editing an existing one is O(n)?Because a cumulative total depends only on the values before it. Appending adds a position that nothing already stored refers to, so you extend by one entry — last total plus the new value — and everything existing stays valid. Editing position i changes the total at i and every position after it, so a suffix of the array must be swept. That single asymmetry is why append-only ledgers suit this structure and back-dated corrections destroy it.
- Reads and writes are both heavy. What do you reach for, and what do you give up?Neither extreme works: rebuilding costs O(n) per write, scanning costs O(n) per read. You want a range structure that supports logarithmic update and logarithmic query, accepting a worse constant factor and noticeably more code than a flat array of totals. What you give up is the thing that makes prefix arrays attractive — a query is no longer a single subtraction, and the implementation is no longer something a reviewer verifies at a glance.
- You rebuild the array nightly instead of on every write. What have you actually decided?You have chosen a staleness window and made it a product decision rather than an implementation detail. Reports can lag by up to a day, so the contract must say so and the response should carry the snapshot's timestamp. In exchange, writes stay O(1) and the rebuild moves off the request path. The failure mode to design for is a rebuild that fails silently, leaving reads served from an increasingly old snapshot with no signal.
- How would you validate the break-even in your own system rather than trusting the model?Measure the real read-to-write ratio and the distribution of n, then benchmark both paths on representative data. The model ignores locality, and a prefix build is a single sequential pass with excellent cache behaviour, so it usually beats the asymptotics at moderate n. Also measure memory, since the duplicated array with wider accumulators is often the binding constraint before time is.
It is a printed index at the back of a book. Wonderful while the book is finished; agony if someone keeps inserting paragraphs in chapter two, because every page number after it is now wrong.
saying these in an interview costs you the question
- Builds the prefix array for a single one-off query
- Says updates are fine because the fix-up is just arithmetic
- Treats appending and editing as equally expensive
- Ignores the O(n) memory duplication entirely
- Claims precomputation is always the better answer for ranges
- Never asks about the read-to-write ratio before choosing