· By John Kavanagh

Range Sum Query: Pay Once for the Prefixes

A yellow numbered measuring tape extends from a metal housing across a pale surface.
Image by William Warby, licensed from Unsplash.

Adding a stretch of an array is straightforward. Repeatedly adding overlapping stretches is where the unnecessary work starts. If the values don't change, we can pay for their cumulative totals once and answer every later range query with one subtraction.

I like Range Sum Query because it rewards being precise about an index. Most incorrect versions are very nearly correct: they include one element too many, omit the right endpoint, or introduce a special case for the first element that the representation could have avoided.

The immutable range‑sum problem on LeetCode asks for a NumArray class whose sumRange(left, right) method includes both endpoints. We'll store prefix totals at positions between elements, giving zero a proper place in the array and leaving the query method pleasantly uneventful.


What Repeated Queries Cost

A direct implementation loops from left through right and adds the values. That costs time proportional to the queried range length. It's easy to read and often entirely appropriate for one query.

With q queries over an array of length n, the worst‑case work becomes O(n × q). If the ranges overlap heavily, we add many of the same values again and again. The immutability promise means those repeated additions cannot discover anything new.

A prefix array uses O(n) preparation time and O(n) additional storage, then answers each query in O(1) time. Across all queries, that is O(n + q) work. The improvement comes from reusing a summary, not from making addition itself more impressive.

I wouldn't automatically allocate the prefix array for a single short query. Precomputation is a trade‑off with a workload, not a badge of algorithmic seriousness. Here, repeated queries and fixed input values make that trade‑off a good fit.


Put Totals Between the Elements

Define prefix[k] as the sum of the first k input elements. The empty prefix has length zero, so prefix[0] = 0. The complete input total lives at prefix[n], giving an array of length n + 1.

For input 4, -2, 7, 0, 3, the table is:

Prefix lengthElements includedTotal
0None0
144
24, ‑22
34, ‑2, 79
44, ‑2, 7, 09
54, ‑2, 7, 0, 312

To answer the inclusive range from index one to index three, take the prefix ending after index three and remove the prefix ending before index one. That is prefix[4] - prefix[1], or 9 - 4 = 5.

The general formula is prefix[right + 1] - prefix[left]. The plus one belongs to the right endpoint because the query includes that element. The left endpoint has no plus one because everything strictly before it is what we want to remove.

Negative values cause no difficulty. We aren't relying on totals increasing, only on cancellation: subtracting the same initial segment leaves the requested segment. Prefix sums work even when the cumulative total falls or repeats.


The Zero Slot Removes a Branch

For a range beginning at zero, the formula subtracts prefix[0], which is already zero. We don't need a special conditional to avoid indexing left - 1.

For a single element at index i, the result is prefix[i + 1] - prefix[i]. For the whole array, it is prefix[n] - prefix[0]. The same expression handles both extremes.

This is why I prefer the extra slot over an array whose cells mean "sum through this index". Both representations can work, but the padded version aligns naturally with half‑open prefixes and removes a recurring edge case from the query method.

The public method still accepts inclusive endpoints because that's what the problem requests. Internally, the prefix length describes a half‑open interval beginning at zero. Keeping those two conventions explicit is easier than trying to make every index mean the same thing.


Complete TypeScript Implementation

class NumArray {
  private readonly prefix: number[];

  constructor(nums: number[]) {
    this.prefix = Array(nums.length + 1).fill(0);
    nums.forEach((value, index) => {
      this.prefix[index + 1] = this.prefix[index] + value;
    });
  }

  sumRange = (left: number, right: number): number =>
    this.prefix[right + 1] - this.prefix[left];
}

The constructor builds a new array and doesn't modify nums. It also doesn't retain a reference to the original values. If the caller later changes their array, this object's answers still describe the values seen during construction.

That snapshot behaviour is deliberate. The problem supplies immutable data, and a real application should decide whether it wants a snapshot or a live view before adopting this structure. Silently expecting it to track external changes would produce stale answers with no warning.

The readonly field prevents ordinary TypeScript code from replacing the prefix property. It doesn't freeze the contents of the array at runtime. We simply keep that array private and expose no mutating operation. Type‑level intent and runtime object freezing are different mechanisms.

The method uses an arrow field, which preserves its instance binding if passed as a callback. The class shape matches the judge's interface; there's no need to turn a naturally small constructor into a factory solely to avoid class syntax.


Know the Arithmetic You're Caching

Under the stated constraints, there are at most 10,000 elements and each has magnitude at most 100,000. Any prefix or range sum therefore has magnitude at most one billion, comfortably within JavaScript's exact integer range.

That argument depends on the input bounds. If the source values were large financial integers or arbitrary‑precision quantities, the numeric representation would need review. If they were decimal fractions, ordinary floating‑point cancellation could introduce rounding effects, even though the algebra remains valid.

Caching a calculation doesn't improve its numeric accuracy. It only changes when and how often we perform it. I would establish the required arithmetic before using prefix totals as a reusable application abstraction.


Verify Every Shape of Range

The simplest independent reference adds the requested elements directly. For short generated arrays, compare every valid pair of endpoints with that reference. This thoroughly exercises the offset formula without reproducing it in the expected‑value calculation.

Include all‑negative arrays, zeroes, alternating signs, a single element, and repeated values. Specifically retain first‑element, last‑element, whole‑array, and interior ranges. A test suite containing only ranges beginning at zero may never notice that the subtraction index is wrong.

Another useful property splits a range at an interior point. The sum of the two adjacent pieces should equal the sum of the full range. Query order should not affect any answer. If snapshot behaviour is intended, mutating the caller's original array after construction should leave existing query results unchanged.

Those properties supplement direct reference checks rather than replacing them. A method returning zero for every range would satisfy the splitting property very nicely, which says more about the property than the method.

My Subarray Sum Equals K article combines prefix totals with a map to count ranges rather than answer a supplied one. My Product of Array Except Self walkthrough uses prefix and suffix information for a different operation, with different rules about what can be cancelled.


When the Input Starts Changing

Updating one source value invalidates every later prefix. A plain prefix array can rebuild those totals, but frequent updates remove the cheap‑query advantage from the combined workload. Structures such as Fenwick trees and segment trees address a different balance between updates and queries.

For this immutable problem, that extra machinery would solve work we haven't been asked to do. A padded prefix array is enough: one clear meaning for each cell, one preparation pass, and one subtraction whose endpoints we can explain without squinting.


Untangling a delivery problem?

Send the symptoms, constraints, and affected routes. I'll help identify whether the issue sits in the application, platform, content model, deployment path, or search surface.