Prefix Sum Array in DSA C

Mental Model

A prefix sum array stores sums of elements from the start 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 these buckets.

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

Dry Run Walkthrough

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

Goal: Build a prefix sum array where each element is the sum of all elements before it including itself

Step 1: Start with prefix[0] = array[0]

Prefix sums: [2] -> null

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

Step 2: Calculate prefix[1] = prefix[0] + array[1] = 2 + 4

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

Why: Add current element to sum of all previous elements

Step 3: Calculate prefix[2] = prefix[1] + array[2] = 6 + 6

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

Why: Keep adding current element to running total

Step 4: Calculate prefix[3] = prefix[2] + array[3] = 12 + 8

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

Why: Continue accumulating sums

Step 5: Calculate prefix[4] = prefix[3] + array[4] = 20 + 10

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

Why: Final prefix sum includes all elements

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void buildPrefixSum(int* arr, int n, int* prefix) {
    if (n == 0) return; // handle empty array gracefully
    prefix[0] = arr[0]; // start with first element
    for (int i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1] + arr[i]; // add current element to previous sum
    }
}

void printArray(int* arr, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i != n - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr[] = {2, 4, 6, 8, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    int* prefix = (int*)malloc(n * sizeof(int));

    buildPrefixSum(arr, n, prefix);

    printf("Original array: ");
    printArray(arr, n);

    printf("Prefix sums:    ");
    printArray(prefix, n);

    free(prefix);
    return 0;
}

prefix[0] = arr[0]; // start with first element

initialize prefix sum with first element of array

for (int i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + arr[i]; // add current element to previous sum }

accumulate sums by adding current element to previous prefix sum

Output

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

Prefix sums:    2 -> 6 -> 12 -> 20 -> 30 -> 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 as input

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

no prefix sums are created; code should handle gracefully

DSA C

for (int i = 1; i < n; i++) { ... } handles zero iterations if n=0

single element array

prefix sum array equals the original single element

DSA C

prefix[0] = arr[0]; handles single element initialization

When to Use This Pattern

When you need to quickly find sums of parts of an array multiple times, use prefix sums to speed up repeated sum queries.

Common Mistakes

Mistake: Starting prefix sum from index 1 without initializing prefix[0]
Fix: Always set prefix[0] = arr[0] before the loop to avoid incorrect sums

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

Summary

It builds an array where each position holds the sum of all elements up to that position.

Use it when you want to find sums of any subarray quickly after one-time setup.

The key is to keep adding the current element to the sum of all previous elements.

Practice

1. What is the main purpose of a prefix sum array in data structures?

easy

A. To quickly find the sum of elements in any subarray

B. To sort the array elements in ascending order

C. To store the product of all elements

D. To reverse the array efficiently

Solution

1. Step 1: Understand prefix sum array definition

   A prefix sum array stores sums of elements from the start up to each index.

2. Step 2: Identify its use

   This allows quick calculation of sums for any subarray by subtracting prefix sums.

3. Final Answer:

   To quickly find the sum of elements in any subarray -> Option A

4. Quick Check:

   Prefix sum = fast subarray sums [OK]

Hint: Prefix sums help find subarray sums fast [OK]

Common Mistakes:

• Confusing prefix sum with sorting
• Thinking it stores products
• Assuming it reverses arrays

2. Which of the following is the correct way to initialize a prefix sum array prefix for an integer array arr of size n in C?

easy

A. prefix[0] = arr[1]; for(int i=1; i

B. prefix[0] = arr[0]; for(int i=1; i

C. for(int i=0; i

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

Solution

1. Step 1: Initialize first prefix element

   Set prefix[0] to arr[0] to start sums correctly.

2. Step 2: Loop from 1 to n-1 adding previous prefix and current arr

   Use prefix[i] = prefix[i-1] + arr[i] for correct cumulative sums.

3. Final Answer:

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

4. Quick Check:

   Start at arr[0], add cumulatively [OK]

Hint: Start prefix with arr[0], then add cumulatively [OK]

Common Mistakes:

• Starting prefix at 0 and indexing arr out of bounds
• Copying arr directly without summing
• Using wrong starting index for arr

3. Given the array arr = {2, 4, 6, 8}, what is the prefix sum array after running the code:

int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i < 4; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. [0, 2, 6, 12]

B. [2, 4, 6, 8]

C. [2, 6, 12, 20]

D. [2, 8, 14, 22]

Solution

1. Step 1: Calculate prefix[0]

   prefix[0] = arr[0] = 2

2. Step 2: Calculate prefix sums for i=1 to 3

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

3. Final Answer:

   [2, 6, 12, 20] -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Confusing prefix sums with original array
• Starting sums from zero incorrectly
• Adding wrong elements in loop

4. Identify the error in the following code snippet that attempts to create a prefix sum array for arr of size n:

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

medium

A. prefix[0] should be initialized to arr[0], not 0

B. Loop should start from i = 0, not 1

C. Array prefix should be of size n+1

D. The code will cause a runtime error

Solution

1. Step 1: Check prefix[0] initialization

   prefix[0] must hold arr[0] to start sums correctly, not zero.

2. Step 2: Analyze loop correctness

   Loop starting at 1 is correct if prefix[0] is set properly.

3. Final Answer:

   prefix[0] should be initialized to arr[0], not 0 -> Option A

4. Quick Check:

   prefix[0] = arr[0] starts sums right [OK]

Hint: Initialize prefix[0] with arr[0], not zero [OK]

Common Mistakes:

• Setting prefix[0] to zero causes wrong sums
• Starting loop at wrong index
• Assuming prefix array size must be n+1

5. You have an array arr = {3, 1, 4, 1, 5, 9, 2}. Using a prefix sum array, how would you efficiently find the sum of elements from index 2 to 5 (inclusive)?

hard

A. Calculate prefix[5] + prefix[2]

B. Sum elements from arr[2] to arr[5] directly every time

C. Use prefix[6] - prefix[2] to get the sum

D. Calculate prefix[5] - prefix[1] after building prefix sums

Solution

1. Step 1: Build prefix sum array

   prefix[i] = sum of arr[0] to arr[i]. For example, prefix[5] = sum of arr[0..5].

2. Step 2: Calculate sum from index 2 to 5

   Sum = prefix[5] - prefix[1], because prefix[1] = sum of arr[0..1].

3. Final Answer:

   Calculate prefix[5] - prefix[1] after building prefix sums -> Option D

4. Quick Check:

   Sum(i..j) = prefix[j] - prefix[i-1] [OK]

Hint: Sum subarray = prefix[end] - prefix[start-1] [OK]

Common Mistakes:

• Adding prefix sums instead of subtracting
• Using wrong indices for prefix subtraction
• Summing elements directly ignoring prefix sums