Prefix Sum

The Prefix Sum pattern is a powerful optimization technique that transforms

O(N)

range queries into

O(1)

constant-time lookups. It essentially involves pre-calculating cumulative totals so you don’t have to re-add elements every time you need a sum.

Real-World Analogy

Imagine you are tracking your monthly spending for a year.

Without Prefix Sum: If someone asks, “How much did you spend from March to July?”, you have to open your ledger and add up: March + April + May + June + July.
With Prefix Sum: You keep a running total at the bottom of each page.
- Jan Total: $100
- Feb Total (Jan+Feb): $250
- …
- July Total (Jan…July): $900
- …
- By February (Jan…Feb): $250

To answer “March to July”, you simply take the July Year-To-Date Total ($900) minus the February Year-To-Date Total ($250). Result: $650. You did just one subtraction instead of adding 5 months.

Visual Explanation

Let’s visualize how the array transforms using a Mermaid diagram.

  graph TD
    subgraph Input [Input Array: nums]
        N0[3]
        N1[1]
        N2[4]
        N3[2]
        N4[5]
    end

    subgraph Prefix [Prefix Sum Array: P]
        P0[0]
        P1[3]
        P2[4]
        P3[8]
        P4[10]
        P5[15]
    end

    %% Edge connections showing accumulation
    P0 --> P1
    N0 --> P1
    P1 --> P2
    N1 --> P2
    P2 --> P3
    N2 --> P3
    P3 --> P4
    N3 --> P4
    P4 --> P5
    N4 --> P5

    style N0 fill:#f9d,stroke:#333
    style P0 fill:#aaf,stroke:#333

Explanation:

P[0] starts as 0.
P[1] is P[0] + nums[0] (0 + 3 = 3).
P[2] is P[1] + nums[1] (3 + 1 = 4).
And so on…

Query: Sum of nums from index 2 to 4 (values 4, 2, 5).

Target range: [2, 4] (inclusive).
Formula: P[right + 1] - P[left]
Operation: P[5] - P[2]
Values: 15 - 4
Result: 11 (Check: 4 + 2 + 5 = 11)

When to Use Prefix Sum

Use this pattern when you see these characteristics:

Input is a static array (doesn’t change often)
Multiple indices range queries (sum OR product)
Subarray sum problems (e.g. “Find subarray that sums to K”)
Need to optimize
O(N^2)
nested loops to
O(N)
or
O(1)

Complexity Analysis

Operation	Time Complexity	Space Complexity	Explanation
Preprocessing	O(N)	O(N)	We iterate through the array once to build the prefix array. We store $N+1$ integers.
Range Query	O(1)	O(1)	Simple subtraction of two values.
Space Optimization	N/A	O(1)	If we can overwrite the input array (mutate it), we don’t need extra space.

Derivation:

Time: Building the array takes one pass
O(N)
. Each query accesses two array indices, which is constant time
O(1)
.
Space: A new array of size $N+1$ is required, hence
O(N)
.

Common Mistakes

Off-by-One Errors: Forgetting that the prefix array is usually size N+1 to handle the empty prefix (0).
Zero-Indexing Confusion: prefix[i] usually sums up to nums[i-1]. Accessing prefix[i] when you mean “sum up to index i” usually requires prefix[i+1].
Integer Overflow: In languages like C++ or Java, the cumulative sum can easily exceed MAX_INT. Use long or long long.