Overview

A prefix sum array stores, at position i, the total of the first i elements. The sum of any range [l, r] is then prefix[r + 1] − prefix[l]: two lookups instead of a loop. Building the array is O(n) once; every query afterwards is O(1).

The idea generalises beautifully. Combined with a hash map of previously seen prefix sums, it counts subarrays summing to k in one pass — even with negative numbers, where sliding windows fail. Run it backwards and you get the difference array, which applies many range updates in O(1) each.

Key concepts

Tick a concept once you can explain it in your own words without notes.

Complexity cheat sheet

OperationCost
Build prefix arrayO(n)
Range sum queryO(1)
2D build / queryO(m·n) / O(1)
Range update with difference arrayO(1) each, O(n) to finalise

Patterns to recognise

Many range queries, no updates

Use it for: Range sum query, pivot index.

Build once, answer each query in O(1).

Count subarrays with a property

Use it for: Sum equals k, sum divisible by k.

Keep a map from prefix value (or prefix mod k) to how often it has occurred.

Batch of range updates

Use it for: Booking systems, car pooling, flight bookings.

Mark boundaries in a difference array, then sweep once.

Code template

Count subarrays whose sum equals k
from collections import defaultdict


def subarray_sum(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                 # empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

Common mistakes

  • Forgetting to seed the map with prefix 0 → 1 misses subarrays that start at index 0.
  • Updating the map before querying it can count an empty subarray.
  • Prefix sums overflow 32-bit integers on large inputs.
  • If the array changes between queries, plain prefix sums go stale — use a Fenwick tree (see Range Queries).

Quick check

Three questions on Prefix Sums. Get all three right to earn +15 XP.

  1. With prefix[0] = 0 and prefix[i] = sum of the first i elements, the sum of arr[l..r] (inclusive) is:

  2. After O(n) preprocessing, each range-sum query costs:

  3. Counting subarrays that sum to k in O(n) combines prefix sums with:

Challenges

Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.

Stuck on Prefix Sums?Ask Orbi for a hint, a fresh explanation or a review of your code.

Ask the tutor