Typorithm · easy

Prefix Sums

prefix-sumspatternsrange-queryprecompute

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Prefix Sums

Basic Patterns

Precompute running totals once; answer any range sum with one subtraction.

prefix[i] stores the sum of the first i values, with prefix[0] = 0.

The sum of arr[left..right] equals prefix[right + 1] - prefix[left].

One O(n) build turns every later range question into O(1).

Seed with 0 to avoid edge cases.

Build is one pass of running totals.

Range sum = two lookups, one subtraction.

function buildPrefix(arr) {
  const prefix = [0];

  for (let i = 0; i < arr.length; i++) {
    prefix.push(prefix[i] + arr[i]);
  }

  return prefix;
}

function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Zero seed

Starting with 0 makes every range formula uniform, even from index 0.

const prefix = [0]

2. Running total

Each entry extends the previous total by one value.

prefix.push(prefix[i] + arr[i])

3. Range formula

Subtracting two totals isolates the sum between left and right.

return prefix[right + 1] - prefix[left]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.