Prefix sum or segment tree?
“You must answer many range-sum queries on an array. When is a prefix-sum array enough, and when do you need a segment tree or Fenwick tree?”
What this tests
- Whether the candidate asks the deciding question: are there updates?
- Understanding of the cost table: build, query, update for each structure.
- Knowledge of which operations each structure supports (sum vs min/max, point vs range update).
- Restraint — not reaching for the heavy structure when the light one suffices.
Strong answer
The deciding question is does the array change between queries? If not, a Prefix Sum array answers any range sum in O(1) after O(n) build; sum(l, r) = P[r+1] - P[l]. It is the simplest correct answer and a strong candidate says so before mentioning anything else.
If there are point updates interleaved with queries, a prefix array costs O(n) per update to rebuild, which is too slow for 10^5 mixed operations. A Fenwick Tree gives O(log n) point update and O(log n) prefix query in a few lines and O(n) memory. A Segment Tree gives the same bounds with more code but supports any associative operation — min, max, gcd — and, with lazy propagation, range updates in O(log n).
They also mention the middle ground: many range updates followed by one read is a Difference Array problem in O(n + q); and static range min queries can use a Sparse Table with O(1) query after O(n log n) build. The choice is a table: static sum → prefix; static min → sparse table; point update + sum → Fenwick; point update + arbitrary associative op → segment tree; range update + range query → lazy segment tree.
Green flags · Red flags
- Asks "are there updates?" first.
- Gives the complexity table for build, query, and update.
- Prefers the simplest structure that meets the requirements.
- Knows Fenwick handles sums/prefix-invertible operations but not min, and why.
- Mentions difference arrays and sparse tables as the other corners of the space.
- Proposes a segment tree for a static array.
- Cannot state the prefix-sum formula with correct indices.
- Does not know that a Fenwick tree cannot answer range minimum.
- Believes range update on a plain segment tree is
O(log n)without lazy propagation.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
10^5 of each.