LESSON 7 · PATTERN GUIDE

Prefix Sum / Running Sum

Precompute cumulative totals so range sums and counting conditions can be answered efficiently.

FIRST, LEARN THE PATTERNA prefix sum stores the total before or through each index. A range sum can be computed by subtracting two prefixes.

Many range-sum queries are asked, or the prompt asks how many subarrays match a sum or remainder condition.

How to approach it

Build prefix[i + 1] = prefix[i] + values[i]. For target subarray sums, count earlier prefixes that differ by the target.

Watch out for

The empty prefix at index zero is essential for ranges beginning at the first element. Remainders with negative sums need normalization.

A CLOSER EXPLANATION

Store a cumulative total at each boundary between elements. A range total is the prefix at its right boundary minus the prefix before its left boundary. For subarray counting, the current prefix can be paired with an earlier prefix that differs by the target; a frequency map lets you count those earlier states.

NOW YOU TRY

Practice question

Find the sum of elements from index 1 through index 3, inclusive, in [3, -1, 4, 2, 5].

EXAMPLEvalues = [3, -1, 4, 2, 5], left = 1, right = 3Give your answer before revealing the explanation.

Show a hint

Subtract the prefix before index 1 from the prefix after index 3.

Show an answer

5, because -1 + 4 + 2 = 5.

CONNECT IT TO REAL LIFE

Prefix Sum / Running Sum at work

A bank records daily net changes [10, -3, 5, -2]. What was the total account change from day 2 through day 4, inclusive?

Show one possible approach

0. The range is -3 + 5 - 2 = 0. Prefix totals let the bank answer many different date-range queries quickly after one preprocessing pass.

Practice next

Use these problem IDs to find additional practice for this pattern:

303560724930974523