1. Concept library
  2. Data Structures & Algorithms
  3. Module 2: Arrays and strings

Concept

Prefix sums

A prefix sum array stores the running total up to each index, so the sum of any range is one subtraction. Build it once in O(n) and answer range queries in O(1).

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain how a prefix sum array answers a range sum in one subtraction
  2. Build a prefix array with a leading zero and query it
  3. Spot the off-by-one from a prefix array without the leading zero

In practice

A few lines that show Prefix sums doing its job.

Python
nums = [3, 1, 4, 1, 5, 9]
prefix = [0]
for n in nums:
    prefix.append(prefix[-1] + n)

def range_sum(i, j):            # sum of nums[i..j] inclusive
    return prefix[j + 1] - prefix[i]

range_sum(1, 3)                 # 1 + 4 + 1 = 6

The common mistake

Watch for

Off-by-one errors from starting the prefix array at the first element instead of 0. Starting with a leading 0 makes every range formula prefix[j+1] - prefix[i], with no special case for i = 0.

What to know first

Your roadmap puts these before Prefix sums, unless you already know them.

How it stays learned

Once a session shows you understand Prefix sums, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Sliding window