What is a prefix sum array?

An array P where P[i] is the sum of the first i elements, with P[0] = 0. Any range sum from L to R is then P[R+1] - P[L], one subtraction instead of a loop.

When is a prefix sum faster than looping?

When the same array answers many range queries. Looping costs O(R - L + 1) per query; building P costs O(N) once, after which every query is O(1), so Q queries cost O(N + Q) instead of O(N × Q).

Why add a leading zero to the prefix array?

With P[0] = 0 the formula P[R+1] - P[L] works for every range, including ranges that start at index 0. Without it, L = 0 needs a special case because P[L-1] does not exist.

Introduction to Prefix Sums

Master the technique to perform range queries in constant time.

Easy

10 min

Solve on LeetCode

What is a Prefix Sum?

A Prefix Sum array stores the cumulative sum of elements up to each index.

P[i] = A[0] + A[1] + ... + A[i].

It transforms array data to allow for rapid range calculations.

The Motivation: Range Queries

You have an array of daily sales: [10, 20, 5, 30, ...].

Query: "What was the total sales from Day 3 to Day 10?"
Query: "What about Day 2 to Day 8?"

If you have millions of queries, loop summing is too slow.

Attempt 1: Brute Force Loop

For each query [L, R], we loop for (i = L; i <= R; i++) sum += A[i].

Complexity: O(N) per query. Total O(Q * N). Too slow!

Visualizing Brute Force Slowness

Switch the figure further down to Loop per query to watch this: overlapping ranges add the same elements again for every query.

When to use Prefix Sum?

Pattern Recognition Triggers:

Subarray Sums: "Find sum of subarray..."
Range Queries: "Calculate value between indices L and R."
Product of Range: use a prefix product, as long as the array has no zeros — the answer is recovered by division.

The Intuition: Subtraction

We can find the sum of [L, R] by taking the sum of everything from 0 to R and subtracting the sum of everything from 0 to L-1.

Sum(L, R) = PrefixSum[R] - PrefixSum[L-1].

The code below stores one extra leading 0, so P[i] is the sum of the first i elements and the same query reads P[R+1] - P[L] — with no special case when L = 0.

This is O(1)!

Interactive Prefix Sum

3 QUERIES ON 6 VALUES

NEW QUERY

nums

Work

Query

[0, 3]

Running sum

Answers

No query answered yet

Query 1: sum nums[0..3] from scratch

Add nums[0] = 3: running sum 3

Array

Queries

Legend & Complexity

Loop: the element being added. Prefix: the P slot written, or P[R+1]

The query’s range in nums, and P[L]

R+1

Pointers name the two P cells a query subtracts

Loop per query

O(N·Q)

Prefix sums

O(N + Q)

Space

O(N)

Compare the two methods on the same queries: Loop per query adds every element of every range, while Prefix sums builds P once and answers each query with one subtraction. Work counts the additions and subtractions each makes.

Dry Run Table

Array: [3, 1, 4]. Prefix with the leading zero: P = [0, 3, 4, 8].

Query	Formula `P[R+1] - P[L]`	Calculation	Result
Sum(1, 2)	`P[3] - P[1]`	8 - 3	5
Sum(0, 1)	`P[2] - P[0]`	4 - 0	4

Solution Template

Precompute P, then calculate difference.

Introduction to Prefix Sums Code

1class NumArray {
2    constructor(nums) {
3        this.P = new Array(nums.length + 1).fill(0);
4        for (let i = 0; i < nums.length; i++) {
5            this.P[i + 1] = this.P[i] + nums[i];
6        }
7    }
8
9    sumRange(left, right) {
10        return this.P[right + 1] - this.P[left];
11    }
12}

Edge Cases & Checks

Common pitfalls:

Index L=0: P[L-1] becomes P[-1]. Use a padding 0 at the start of array to handle this easily.
Overflow: Sums might exceed Integer limits (use Long).
Mutable Array: If array changes, Prefix Sum must be rebuilt (use Segment Tree instead).

Summary

Recap: Preprocessing data allows for O(1) answers. This is a fundamental trade-off in algorithm design.

Count Vowels in Ranges