DATA STRUCTURES • ALGORITHMS

Prefix Sum

A precomputation technique where an auxiliary array is created such that each element at index i stores the sum of all elements from the start up to i.

Time

O(N) (Precompute)

Space

O(N)

Key Principle 1

Enables O(1) range sum queries

Key Principle 2

Sum[L..R] = Prefix[R] - Prefix[L-1]

Key Principle 3

Space-Time tradeoff

Key Principle 4

Essential for competitive programming

PREFIX_SUM_LAB
ARRAY:
Current Step
Initialize prefix sum array P of same size.
Playback
Sum Tracker ⠿
SIZE5
STATUSStarted
Prefix Sum Logic ⠿
1int P[n];
2P[0] = arr[0];
3for (int i = 1; i < n; i++) {
4    P[i] = P[i - 1] + arr[i];
5}
1
[0]
2
[1]
3
[2]
4
[3]
5
[4]
?
P[0]
?
P[1]
?
P[2]
?
P[3]
?
P[4]

Loading Lab...

Prefix Sum Basics

Prefix Sum Basics

Prefix Sum

Prefix Sum