Learn the vocabulary of a tree of range summaries that answers a query by combining a handful of nodes.
0 / 5 completed
1 / 5
At standup, a dev mentions a binary tree built over an array where each node stores a summary, like a sum, minimum, or maximum, of a contiguous range of elements, letting a range query be answered by combining just a handful of node summaries. What is this structure called?
A segment tree is exactly this: a binary tree built over an array where each node stores a summary, such as a sum, minimum, or maximum, of a contiguous range of the underlying elements, so a query over any arbitrary range can be answered in logarithmic time by combining a small number of precomputed node summaries instead of scanning every element in that range. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This precomputed-range-summary structure is exactly why a segment tree efficiently supports both range queries and point updates.
2 / 5
During a design review, the team relies on a segment tree specifically so updating a single element only requires recomputing summaries along one root-to-leaf path, rather than recomputing every range summary in the whole structure. Which capability does this provide?
A segment tree here provides logarithmic-time updates, since changing a single element only invalidates the summaries stored in that leaf's ancestors, a single root-to-leaf path, and only those need to be recomputed, leaving every other summary in the structure untouched and still valid. Recomputing every range summary in the entire structure after every single point update would cost far more, proportional to the whole array's size instead of just its height. This localized-recomputation behavior is exactly what lets a segment tree support a heavy mix of range queries and point updates efficiently.
3 / 5
In a code review, a dev notices a range-sum feature recomputes the sum of the requested range by iterating over every element in that range directly, on every single query, with no precomputed summary structure at all. What does this represent?
This is a missed segment-tree opportunity, since scanning every element in the requested range on every single query costs time proportional to the range's size, when a segment tree's precomputed node summaries would let the same query be answered in logarithmic time by combining just a handful of summaries instead. A cache eviction policy is an unrelated concept about discarded cache entries. This scan-every-time pattern is exactly the kind of inefficiency a reviewer flags once range queries become frequent enough that repeatedly rescanning the same elements adds up.
4 / 5
An incident report shows an analytics endpoint answering range-sum queries over a large, frequently-updated dataset slowed sharply under load, because every query scanned every element in the requested range directly instead of using a precomputed summary structure. What practice would prevent this?
Building a segment tree over the dataset lets each range-sum query be answered in logarithmic time by combining a small number of precomputed node summaries, instead of rescanning every element in the requested range, which is exactly the fix for the slowdown described in this incident. Continuing to scan every element directly on every single query is exactly what caused performance to degrade sharply as query volume and range sizes grew under load. This precomputed-summary structure is the standard fix once range queries over a large, changing dataset become frequent enough that repeated full scans no longer scale.
5 / 5
During a PR review, a teammate asks why the team builds a segment tree instead of just precomputing a simple prefix-sum array, given that a prefix-sum array also answers range-sum queries very quickly. What is the reasoning?
A prefix-sum array answers a range-sum query almost instantly, but updating even a single element forces a large portion of the array after that point to be recomputed, costing linear time, while a segment tree keeps both range queries and point updates down to logarithmic time by only touching a small ancestor path on each update. The tradeoff is that a segment tree costs more memory and a slightly more involved implementation than a plain prefix-sum array. This is exactly why a prefix-sum array is preferred for a static dataset that never changes, while a segment tree is preferred the moment updates become frequent.