Prefix Sum Array in DSA C++

Mental Model

A prefix sum array stores the sum of all elements up to each position, so you can quickly find the sum of any part of the original array.

Analogy: Imagine a row of buckets where each bucket holds the total amount of water collected from the first bucket up to that bucket. To find how much water is between two buckets, you just subtract the amounts in the buckets.

Original array:  [2] -> [4] -> [6] -> [8] -> null
Prefix sums:     [2] -> [6] -> [12] -> [20] -> null

Dry Run Walkthrough

Input: array: [2, 4, 6, 8]

Goal: Build a prefix sum array to quickly find sums of subarrays

Step 1: Start with prefix sum array first element same as original

Prefix sums: [2] -> null

Why: The first prefix sum is just the first element itself

Step 2: Add second element to previous prefix sum: 2 + 4 = 6

Prefix sums: [2] -> [6] -> null

Why: Each prefix sum includes all elements up to that index

Step 3: Add third element to previous prefix sum: 6 + 6 = 12

Prefix sums: [2] -> [6] -> [12] -> null

Why: Keep accumulating sums to build prefix sums

Step 4: Add fourth element to previous prefix sum: 12 + 8 = 20

Prefix sums: [2] -> [6] -> [12] -> [20] -> null

Why: Final prefix sum includes all elements

Result:

Prefix sums: [2] -> [6] -> [12] -> [20] -> null

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Function to build prefix sum array
vector<int> buildPrefixSum(const vector<int>& arr) {
    vector<int> prefixSum(arr.size());
    if (arr.empty()) return prefixSum; // handle empty array

    prefixSum[0] = arr[0]; // first prefix sum is first element
    for (size_t i = 1; i < arr.size(); ++i) {
        prefixSum[i] = prefixSum[i - 1] + arr[i]; // add current element to previous sum
    }
    return prefixSum;
}

// Function to print array in arrow format
void printArray(const vector<int>& arr) {
    for (size_t i = 0; i < arr.size(); ++i) {
        cout << arr[i];
        if (i != arr.size() - 1) cout << " -> ";
    }
    cout << " -> null" << endl;
}

int main() {
    vector<int> arr = {2, 4, 6, 8};
    vector<int> prefixSum = buildPrefixSum(arr);

    cout << "Original array: ";
    printArray(arr);
    cout << "Prefix sum array: ";
    printArray(prefixSum);

    return 0;
}

prefixSum[0] = arr[0];

Initialize first prefix sum with first element

prefixSum[i] = prefixSum[i - 1] + arr[i];

Add current element to previous prefix sum to build running total

Output

Original array: 2 -> 4 -> 6 -> 8 -> null

Prefix sum array: 2 -> 6 -> 12 -> 20 -> null

Complexity Analysis

Time: O(n) because we visit each element once to build the prefix sums

Space: O(n) because we create a new array to store prefix sums of the same size

vs Alternative: Without prefix sums, summing any subarray takes O(k) time; prefix sums reduce this to O(1) after O(n) preprocessing

Edge Cases

empty array

returns an empty prefix sum array without error

DSA C++

if (arr.empty()) return prefixSum;

single element array

prefix sum array equals the original single element

DSA C++

prefixSum[0] = arr[0];

When to Use This Pattern

When you need to find sums of many subarrays quickly, use prefix sum arrays to avoid repeated addition.

Common Mistakes

Mistake: Starting prefix sum from zero index without initializing first element
Fix: Always set prefixSum[0] = arr[0] before looping

Mistake: Adding current element to arr[i-1] instead of prefixSum[i-1]
Fix: Add to prefixSum[i-1] to accumulate sums correctly

Summary

It builds an array where each element is the sum of all elements before it in the original array.

Use it when you want to quickly find the sum of any part of an array multiple times.

The key is to keep a running total so you don't add the same numbers again and again.

Practice

1. What does a prefix sum array represent for a given array arr?

easy

A. An array where each element is the difference between the current and previous element in arr

B. An array where each element is the product of all elements from the start up to that index in arr

C. An array where each element is the sum of all elements from the start up to that index in arr

D. An array where each element is the maximum value found in arr up to that index

Solution

1. Step 1: Understand prefix sum array definition

   A prefix sum array stores cumulative sums, where each element at index i is the sum of all elements from index 0 to i in the original array.

2. Step 2: Compare options with definition

   Only An array where each element is the sum of all elements from the start up to that index in arr correctly describes this cumulative sum property. Other options describe different operations.

3. Final Answer:

   An array where each element is the sum of all elements from the start up to that index in arr -> Option C

4. Quick Check:

   Prefix sum = cumulative sum [OK]

Hint: Prefix sum means adding elements from start to current index [OK]

Common Mistakes:

• Confusing prefix sum with product or max operations
• Thinking prefix sum stores differences
• Assuming prefix sum resets at each index

2. Which of the following C++ code snippets correctly initializes a prefix sum array prefix from an integer array arr of size n?

easy

A. prefix[0] = 0; for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + arr[i];

B. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i];

C. prefix[0] = arr[0]; for(int i = 0; i < n; i++) prefix[i] = prefix[i-1] + arr[i];

D. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = arr[i] - prefix[i-1];

Solution

1. Step 1: Check initialization of prefix array

   Prefix sum starts with prefix[0] = arr[0], which is correct in options B, C, and D.

2. Step 2: Verify loop and summation logic

   prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; correctly loops from i=1 to n-1 and adds prefix[i-1] + arr[i]. prefix[0] = 0; for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + arr[i]; has wrong indexing and loop range. prefix[0] = arr[0]; for(int i = 0; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; uses prefix[i-1] at i=0 which is invalid. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = arr[i] - prefix[i-1]; subtracts instead of adding.

3. Final Answer:

   prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; -> Option B

4. Quick Check:

   Initialize first, then add previous prefix + current [OK]

Hint: Start prefix[0] = arr[0], then add previous prefix + current [OK]

Common Mistakes:

• Starting loop at 0 and accessing prefix[-1]
• Using wrong loop bounds (<= n instead of < n)
• Subtracting instead of adding elements

3. What is the output of the following C++ code?

int arr[] = {2, 4, 6, 8};
int n = 4;
int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}
for(int i = 0; i < n; i++) {
    std::cout << prefix[i] << " ";
}

medium

A. 2 6 12 20

B. 2 4 6 8

C. 2 8 14 20

D. 2 6 10 18

Solution

1. Step 1: Calculate prefix sums step-by-step

   prefix[0] = 2
   prefix[1] = prefix[0] + arr[1] = 2 + 4 = 6
   prefix[2] = prefix[1] + arr[2] = 6 + 6 = 12
   prefix[3] = prefix[2] + arr[3] = 12 + 8 = 20

2. Step 2: Print prefix array elements

   Output is: 2 6 12 20

3. Final Answer:

   2 6 12 20 -> Option A

4. Quick Check:

   Sum accumulates: 2, 6, 12, 20 [OK]

Hint: Add current element to previous prefix sum each step [OK]

Common Mistakes:

• Printing original array instead of prefix sums
• Incorrect addition order
• Off-by-one errors in loop

4. Identify the error in the following prefix sum array code and select the corrected version:

int arr[] = {1, 3, 5, 7};
int n = 4;
int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. Change loop condition to i < n to avoid out-of-bounds access

B. Initialize prefix[0] = 0 instead of arr[0]

C. Use i = 0 as loop start and keep condition i < n

D. Replace prefix[i] with arr[i] inside loop

Solution

1. Step 1: Analyze loop bounds and array indexing

   The loop runs with i from 1 to n inclusive (i <= n). Since arrays are 0-indexed, prefix[n] and arr[n] access out-of-bounds elements causing runtime error.

2. Step 2: Correct loop condition

   Changing loop condition to i < n ensures indices stay within valid range (0 to n-1).

3. Final Answer:

   Change loop condition to i < n to avoid out-of-bounds access -> Option A

4. Quick Check:

   Loop must stay within array size [OK]

Hint: Loop index must be less than array size, not less or equal [OK]

Common Mistakes:

• Using <= n causing out-of-bounds errors
• Starting loop at 0 and accessing prefix[-1]
• Incorrect initialization of prefix[0]

5. Given an array arr of size n, how can you use a prefix sum array to efficiently find the sum of elements between indices l and r (inclusive)?

hard

A. Sum = prefix[r] / prefix[l-1] if l > 0, else prefix[r]

B. Sum = prefix[r] + prefix[l-1] if l > 0, else prefix[r]

C. Sum = prefix[r] * prefix[l-1] if l > 0, else prefix[r]

D. Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r]

Solution

1. Step 1: Understand prefix sum usage for range queries

   Prefix sum at index r gives sum from 0 to r. To get sum from l to r, subtract sum from 0 to l-1, which is prefix[l-1]. If l is 0, sum is prefix[r].

2. Step 2: Apply formula for sum between l and r

   Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r]. Other operations like addition, multiplication, or division are incorrect.

3. Final Answer:

   Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r] -> Option D

4. Quick Check:

   Range sum = prefix[r] - prefix[l-1] [OK]

Hint: Subtract prefix before l from prefix at r for range sum [OK]

Common Mistakes:

• Adding prefix[l-1] instead of subtracting
• Using multiplication or division incorrectly
• Not handling case when l = 0