What Is the Prefix Sum Technique?

You precompute the running total of the first k elements for every k, then answer questions about any range by subtracting two of those totals. The sum of the elements from index left to index right is the prefix sum at right plus one minus the prefix sum at left.

def prefix_sums(nums):
    sums = [0]
    for value in nums:
        sums.append(sums[-1] + value)
    return sums

data = [2, 3, 5]
sums = prefix_sums(data)
print(sums)
print(sums[2] - sums[0])

The outputs are the list 0, 2, 5, 10 and the number 5. The prefix list has one extra leading zero so that the prefix sum before the first element is well defined, which is what lets you compute the sum of a range starting at index zero without a special case.

The mechanism is that a range sum is a difference of two prefix sums. Precomputing once makes each query a constant-time subtraction instead of a scan over the range, so a program with many range queries over the same array goes from quadratic to linear overall.

The trade-off to name is that the prefix array costs O of n space, and it is only valid for a static array. If the values change, every prefix sum after that point is wrong and the whole array has to be rebuilt, which is linear per update. That is the moment to reach for a Fenwick tree or a segment tree instead: they support both queries and updates in logarithmic time at the cost of a more complex implementation and a larger constant factor. Knowing when the data is static and when it is not is the entire decision.

Precompute the prefix sums once in the constructor, then answer each query with a subtraction. Build the prefix array with a leading zero so that ranges starting at index zero need no special handling.

class RangeSum:
    def __init__(self, nums):
        self.sums = [0]
        for value in nums:
            self.sums.append(self.sums[-1] + value)

    def query(self, left, right):
        return self.sums[right + 1] - self.sums[left]


tracker = RangeSum([2, 3, 5, 7])
print(tracker.query(0, 2))
print(tracker.query(1, 3))
print(tracker.query(2, 2))

The outputs are 10, 15 and 5. The first query covers 2, 3 and 5, the second covers 3, 5 and 7, and the third covers only the 5. Every query is two array reads and a subtraction, regardless of how wide the range is.

The mechanism is the difference of prefix sums, exactly as in the simple version, but the construction is moved into the object so the work happens once and can be shared across many queries. The class exists to make the lifetime of the precomputed data explicit, which matters because that data is only valid while the underlying array is unchanged.

The trade-off to name is that this is the right tool only for a static array. Each update invalidates every later prefix sum, so a rebuild per update costs O of n and the structure degenerates to quadratic if you update as often as you query. A Fenwick tree supports both operations in logarithmic time, and a segment tree supports range sums plus arbitrary aggregates, at the cost of a much longer implementation and worse constants for the static case. Interviewers reward hearing that you would start with prefix sums, measure, and only move to a tree when the update pattern demands it.