Skip to content

Prefix Sum

Lesson 4 of 7 in Core Patterns · 25 min · Beginner

Precompute running totals; any range sum is one subtraction.

Introduction

A fitness app keeps your step count for every day of the year. How can it answer “how many steps between day 3 and day 20?” thousands of times without re-adding every time?

The obvious way adds up days 3 to 20 on every question: 18 additions. A longer stretch means more additions, and the same days get added again and again, once per question.

Now suppose the app also writes down, once and in advance, a running total next to each day: all the steps from day 1 up to that day. Then a question only needs the totals around your stretch. Which two would you look at?

Lesson overview

This lesson will show you how to:

  • Explain why subtracting two running totals gives any stretch's sum.
  • Build a prefix array with a leading zero for inclusive ranges.
  • Trace sum(l..r) as prefix[r + 1] minus prefix[l] on an example.
  • Spot repeated range-sum questions over an array that never changes.
  • Choose prefix sums only for operations you can undo, like sums and counts.

The picture

nums
nums30-1142135495lr12 − 2 = 10Array nums with 6 slots: 3, -1, 4, 1, 5, 9. Pointers: l at index 2; r at index 4. Window from index 2 to 4.
prefix
prefix0031226374125216total up to heretotal before the stretchArray prefix with 7 slots: 0, 3, 2, 6, 7, 12, 21. Marked: index 2 compare; index 5 compare.

Mental model

A car’s odometer shows every kilometre the car has ever driven. To know how far one trip went, you don’t replay the trip: read the odometer when it ends, read it when it started, and subtract.

Each reading already contains everything that came before it, so the part you don’t want cancels out. A prefix array is an odometer reading written next to every number.

Total up to the end, minus total up to just before the start: everything before the stretch cancels.

Words to know

prefix array
A second array, one cell longer than nums, holding running totals. prefix[i] is the sum of the first i numbers.
running sum
The total of everything added so far while you walk along the array. Each prefix cell is one running sum, frozen.
leading zero
prefix[0] = 0: the total of no numbers at all. It is the extra cell that makes a range starting at index 0 work like every other range.
range query
A question about a stretch of the array, like “what is the sum from index 2 to index 4?”. Written sum(l..r).
inclusive range
l..r includes both nums[l] and nums[r]. That is why the formula reaches for prefix[r + 1], not prefix[r].
build
Filling the prefix array once, left to right: prefix[i + 1] = prefix[i] + nums[i]. It costs one pass.
need
In Subarray Sum Equals K: the earlier running sum a stretch ending here would have to start from, which is running sum minus k.

Watch it run

Step with → or Next. When a question pops up, make your guess. Try your own input once the guided run ends.

Getting the demo ready…

Recognise it

Most of the skill is noticing the clue in the problem statement.

Reach for it when

  • Yes: You must answer many questions about the sum (or count, or XOR) of a stretch of the same array.
  • Yes: The array stays the same between questions, so the work done up front is never wasted.
  • Yes: The problem says “subarray sums to k”, “divisible by k” or “equal numbers of 0s and 1s”: a stretch’s total is the difference of two running totals.
  • Yes: A nested loop re-adds the same numbers again and again.

Not this when

  • No: The array changes between questions. A prefix array goes stale after every update, so you would need a structure built for updates, such as a Fenwick tree.
  • No: You need the maximum or minimum of a stretch. Unlike a sum, a maximum can’t be subtracted out.
  • No: One window slides over the data once and you only want its best sum. A sliding window does that with O(1) extra space.

Which pattern fits?

  1. Which pattern? 1 of 5

    An array of daily step counts never changes. You must answer 50,000 questions, each asking for the total between day l and day r.

  2. Which pattern? 2 of 5

    Given an array of numbers and a size k, find the largest sum of any k neighbouring numbers. You are asked once.

  3. Which pattern? 3 of 5

    Given an array that may contain negative numbers and a target k, count how many stretches of neighbouring numbers add up to exactly k.

  4. Which pattern? 4 of 5

    Given a sorted array, find two numbers that add up to a target.

  5. Which pattern? 5 of 5

    In how many different ways can you climb n stairs if you may take 1 or 2 steps at a time?

The code

First the idea in plain steps. Then the same idea as real code, line for line.

Pseudocode
  1. 1prefix = n + 1 cells, with prefix[0] = 0
  2. for each position i in nums:
  3. 2prefix[i + 1] = prefix[i] + nums[i]
  4. for each query (l, r), inclusive:
  5. 3answer = prefix[r + 1] − prefix[l]

The faint numbers are the rules in the Rule Rail under the stage. Same numbers, same order.

Getting the replay ready…

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]
Time · O(n) to build, O(1) per querySpace · O(n)
  • Build once, then q queries cost O(n + q) in total. Re-adding for every query costs up to O(n · q).
  • Use n + 1 cells with prefix[0] = 0, so prefix[i] means “the sum of the first i numbers”. Then sum(l..r) = prefix[r + 1] − prefix[l] for every query, including l = 0. The shorter version, prefix[i] = sum(0..i), needs a special case for l = 0.
  • The range is inclusive, so the right-hand cell is prefix[r + 1]. Reaching for prefix[r] is the classic off-by-one.
  • It works for anything you can undo: sums, counts, XOR. It does not work for max or min, because you can’t subtract a maximum out.
  • The array must not change. If it does, rebuilding costs O(n) each time, so use a structure built for updates instead.
  • Sums can outgrow a 32-bit int on big inputs. Check the constraints, and use a 64-bit type (long in Java, long long in C++) when they are large.

Worked examples

Real interview problems, solved with the same recipe.

Open on LeetCode (opens in a new tab)

Design a class that stores an integer array nums once, then answers many queries sumRange(left, right): the sum of nums[left..right], both ends included.

Input

NumArray([-2, 0, 3, -5, 2, -1]), then sumRange(0, 2), sumRange(2, 5), sumRange(0, 5)

Output

1, -1, -3

Approach

  1. The array never changes and queries repeat, so do the adding once, in the constructor, and make each query cheap.
  2. Build prefix with one extra cell: prefix[0] = 0 and prefix[i + 1] = prefix[i] + nums[i]. Here it is [0, -2, -2, 1, -4, -2, -3].
  3. sumRange(left, right) = prefix[right + 1] − prefix[left]. So sumRange(0, 2) = prefix[3] − prefix[0] = 1 − 0 = 1.
  4. sumRange(2, 5) = prefix[6] − prefix[2] = -3 − (-2) = -1, and sumRange(0, 5) = -3 − 0 = -3. The leading 0 means left = 0 needs no special case.
class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]
Time · O(n) to build, O(1) per querySpace · O(n)

Knowledge check

Test yourself first. Try to answer these in your own words, then take the quiz below to check.

  1. With the n + 1 convention, what is prefix for nums = [4, 2, 7, 1]?
  2. With prefix = [0, 4, 6, 13, 14], what is the sum of nums[1..2]?
  3. You build a prefix array once and then answer q range-sum queries on n numbers. What is the total time?
  4. What does the extra 0 at the front of the prefix array buy us?
  5. In Subarray Sum Equals K, why do we put 0 in the map with a count of 1 before the loop starts?

Question 1 of 5

With the n + 1 convention, what is prefix for nums = [4, 2, 7, 1]?

Assignment

Pick one, try it cold for ten minutes, then come back for the hint.

0 of 8 solved

  1. Solve Running Sum of 1d Array (opens in a new tab) (LeetCode, easy)

    Hint: The answer is the prefix array, almost. Each output is the one before it plus the new number.

  2. Solve Product of Array Except Self (opens in a new tab) (LeetCode, medium)

    Hint: Everything except nums[i] is the product on its left times the product on its right. Build prefix products instead of prefix sums.

  3. Solve Contiguous Array (opens in a new tab) (LeetCode, medium)

    Hint: Count each 0 as -1. Then equal numbers of 0s and 1s means a stretch totals 0, so look for two equal running sums.

  4. Solve Continuous Subarray Sum (opens in a new tab) (LeetCode, medium)

    Hint: Two running sums with the same remainder mod k bound a stretch that is a multiple of k. What should the map remember, and how far apart must the two be?

  5. Solve Subarray Sums Divisible by K (opens in a new tab) (LeetCode, medium)

    Hint: Count how often each running-sum remainder has appeared. Careful: the remainder of a negative sum can come out negative.

  6. Solve Range Sum Query 2D - Immutable (opens in a new tab) (LeetCode, medium)

    Hint: Prefix sums work in two directions. A rectangle is a big rectangle minus two strips, plus the corner you subtracted twice.

  7. Solve Matrix Block Sum (opens in a new tab) (LeetCode, medium)

    Hint: Build the 2D prefix once, then every answer cell is one rectangle query. Clamp the rectangle at the edges of the grid.

  8. Solve Maximum Sum of 3 Non-Overlapping Subarrays (opens in a new tab) (LeetCode, hard)

    Hint: Prefix sums give every window of length k in O(1). Then, for each middle window, you need the best window to its left and the best to its right.

Additional resources