0PricingLogin▼
DSA Interview Prep · Lesson

Prefix Sums and Running Totals

Build prefix-sum arrays to answer range-sum queries in O(1) and apply the technique to subarray problems like maximum-sum subarray.

The Range-Sum Problem

Given an array nums, you need to answer many queries of the form: what is the sum of elements from index i to index j? Computing each query naively takes O(n) time, so k queries cost O(n×k). With a prefix sum array, you precompute a running total in O(n) and then answer each query in O(1). This is one of the most widely used pre-computation techniques in interviews.

# Naive: O(n) per query
def range_sum_naive(nums, i, j):
    return sum(nums[i:j+1])

nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3))  # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4))  # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations

Building the Prefix Sum Array

Define prefix[i] as the sum of nums[0] through nums[i-1] (one extra slot, zero-indexed offset of 1 makes boundary cases cleaner). Build it in O(n) with one pass: prefix[i] = prefix[i-1] + nums[i-1]. Then a range query sum(i, j) becomes prefix[j+1] - prefix[i]: a single subtraction costing O(1).

def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix, i, j):
    return prefix[j+1] - prefix[i]  # O(1)

nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre)                    # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3))  # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15  correct
print(range_sum(pre, 1, 3))  # 15

All lessons in this course

  1. Array Basics and In-Place Operations
  2. Prefix Sums and Running Totals
  3. Two Pointers: Opposite Ends
  4. Two Pointers: Slow and Fast
← Back to DSA Interview Prep