Prefix sums, intervals and sweep lines

Why it matters

Range questions are everywhere: requests in a time window, sessions that overlap, bookings that conflict, load per server after many range updates. Recomputing each answer from scratch costs O(n) per query. Prefix sums, difference arrays and sweep lines move that work into one preprocessing pass or one sorted scan, which is exactly the transformation interviewers hope you find.

Core ideas

Pattern: Prefix sums. Define P[0] = 0 and P[i + 1] = P[i] + a[i]. The sum of a[l..r] (inclusive) is P[r + 1] − P[l]. The leading zero removes the special case for ranges that start at index 0. Building P costs O(n) and each query O(1). The idea extends to counts and XOR, and to products through prefix and suffix arrays (Product of Array Except Self). In two dimensions, S[i][j] holds the sum of the rectangle above and to the left, and any sub-rectangle sum takes four lookups by inclusion and exclusion.

Prefix sums with a hash map. A subarray a[l..r] sums to k exactly when P[r + 1] − P[l] = k. Scan left to right with a map from each prefix value to how often it has occurred; at each step add count[P − k] to the answer, then record P. Seed the map with {0: 1} so subarrays starting at index 0 are counted. This works with negative numbers, where sliding windows fail. Variants store the first index of each prefix (longest subarray with a property) or prefixes modulo k (Continuous Subarray Sum); in languages where % can be negative, normalize the remainder.

Pattern: Sweep line / difference arrays. To add v to every position in [l, r], do D[l] += v and D[r + 1] −= v; after all updates, one prefix pass over D yields the final values. k updates over n positions cost O(n + k) instead of O(n × k) (Car Pooling, Corporate Flight Bookings). When coordinates are large or sparse, turn each interval into two events, (start, +1) and (end, −1), sort them and sweep while tracking the running total; its maximum is the peak number of simultaneous intervals. The tie order encodes your boundary convention: for half-open intervals [start, end), process ends before starts at equal coordinates so that touching intervals do not count as overlapping.

Pattern: Interval merging. Sort by start and keep a current merged interval. If the next interval starts at or before the current end, extend the end to the larger of the two ends; otherwise emit the current interval and start a new one. That is O(n log n) for the sort plus a linear pass. Insert Interval on already sorted input is linear: copy intervals that end before the new one, merge the overlapping ones, copy the rest. To intersect two sorted interval lists, use two pointers and advance whichever interval ends first.

Selection. Keeping the maximum number of non-overlapping intervals is a greedy choice: sort by end and keep each interval that starts after the last kept end. The proof is an exchange argument, covered in the greedy topic.

Limits. Static prefix sums assume no updates. When updates and queries interleave, use a Fenwick (binary indexed) tree or a segment tree with O(log n) per operation; for a dynamic set of intervals with overlap queries, an ordered map keyed by start works.

Common misconceptions

• "Prefix sums need non-negative numbers." They work for any values; it is the sliding window that needs non-negative values.
• "The leading zero is optional." Without P[0] = 0, or {0: 1} in the map, subarrays that start at index 0 are missed.
• "Touching intervals overlap." That depends on whether intervals are closed or half-open; decide, say it, and make comparisons and event tie-breaking match.
• "Sorting by start or by end is interchangeable." Merging sorts by start; selecting the most non-overlapping intervals sorts by end.
• "A difference array answers queries during updates." Values exist only after the prefix pass; interleaved queries need a Fenwick tree or a segment tree.

How to approach it

Ask whether intervals are closed or half-open, whether the input is sorted, and whether updates interleave with queries. Write the prefix definition with explicit indices and check it on a three-element example before coding. For sweeps, write the event tuple and tie-breaking rule down first. Interviewers probe boundary conventions, negative numbers and what changes when the data arrives as a stream rather than a batch.