Skip to content

Prefix Sum

First PublishedByAtif Alam

Difficulty: Easy. ROI: High.

Other common names: Cumulative sum, running sum, scan.

When to use: Use when you need the sum of a subarray (range [i, j]) many times, or when you need to quickly check “is there a subarray with sum k?” (often with a hash map of prefix sums).

Idea: Build an array prefix where prefix[i] = arr[0] + arr[1] + ... + arr[i]. Then the sum of arr[i..j] is prefix[j] - prefix[i-1] (treat prefix[-1] = 0).

Time / space: Build O(n), each range query O(1). Space O(n).

Example #1 — Build Prefix and Range Sum

Section titled “Example #1 — Build Prefix and Range Sum”

Precompute a prefix array so that the sum of any range [i, j] is a single subtraction: prefix[j+1] − prefix[i]. Build by scanning once; each query is O(1).

Sample input and output

arr = [1, 3, 2, 5, 4]
prefix = build_prefix(arr)   # [0, 1, 4, 6, 11, 15]
print(range_sum(prefix, 1, 3))  # 3+2+5 = 10
print(range_sum(prefix, 0, 2))  # 1+3+2 = 6
  • Sample input: arr = [1, 3, 2, 5, 4]; after build_prefix, prefix = [0, 1, 4, 6, 11, 15].
  • Sample output: range_sum(prefix, 1, 3) is 10 (3+2+5); range_sum(prefix, 0, 2) is 6 (1+3+2).

Code (with inline comments)

# Build prefix sum; then sum(arr[i:j+1]) = prefix[j+1] - prefix[i]
def build_prefix(arr):
    prefix = [0]   # prefix[0] = 0 so that prefix[1] = arr[0], etc.
    for x in arr:
        prefix.append(prefix[-1] + x)  # each entry = previous + current element
    return prefix


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

Line-by-line:

  • prefix = [0] — We start with 0 so that prefix[1] = arr[0], prefix[2] = arr[0]+arr[1], and in general prefix[i] = sum of arr[0..i-1]. That way we can express any range sum as a difference of two prefix values.
  • for x in arr: prefix.append(prefix[-1] + x) — We build the array one element at a time. prefix[-1] is the last value (sum so far); adding x gives the sum including the current element.
  • return prefix[j + 1] - prefix[i] — The sum of arr[i] through arr[j] (inclusive) is the sum of the first j+1 elements minus the sum of the first i elements, i.e. prefix[j+1] - prefix[i]. No loop needed — O(1) per query.

Execution trace (numbered list)

For arr = [1, 3, 2, 5, 4]:

  1. Step 0: prefix = [0].
  2. Step 1: x=1, append 0+1 → prefix = [0, 1].
  3. Step 2: x=3, append 1+3 → prefix = [0, 1, 4].
  4. Step 3: x=2, append 4+2 → prefix = [0, 1, 4, 6].
  5. Step 4: x=5, append 6+5 → prefix = [0, 1, 4, 6, 11].
  6. Step 5: x=4, append 11+4 → prefix = [0, 1, 4, 6, 11, 15].
  7. Query range_sum(prefix, 1, 3): prefix[4] − prefix[1] = 11 − 1 = 10.

Execution trace (code with step comments)

arr = [1, 3, 2, 5, 4]
prefix = [0]
# Step 1: x=1  → prefix.append(1)  → [0, 1]
# Step 2: x=3  → prefix.append(4)  → [0, 1, 4]
# Step 3: x=2  → prefix.append(6)  → [0, 1, 4, 6]
# Step 4: x=5  → prefix.append(11) → [0, 1, 4, 6, 11]
# Step 5: x=4  → prefix.append(15) → [0, 1, 4, 6, 11, 15]
# range_sum(prefix, 1, 3) = prefix[4] - prefix[1] = 11 - 1 = 10

Execution trace (ASCII diagram)

arr:    [ 1,  3,  2,  5,  4 ]
prefix: [ 0,  1,  4,  6, 11, 15 ]
         ^   ^       ^   ^
         |   |       |   prefix[4]-prefix[1] = 11-1 = 10 for range [1..3]
         |   +-- sum arr[0..2] = 6
         +------ sum arr[0..0] = 1