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 totals.

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

Dry Run Walkthrough

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

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

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

[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

[2] -> [6] -> null

Why: Each prefix sum adds current element to sum before it

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

[2] -> [6] -> [12] -> null

Why: Keep accumulating sums step by step

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

[2] -> [6] -> [12] -> [20] -> null

Why: Final prefix sum includes all elements

Result:

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

Annotated Code

DSA C#

using System;

class PrefixSumArray
{
    public static int[] BuildPrefixSum(int[] arr)
    {
        int n = arr.Length;
        int[] prefixSum = new int[n];
        if (n == 0) return prefixSum; // handle empty array

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

    public static void PrintArray(int[] arr)
    {
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i != arr.Length - 1) Console.Write(" -> ");
        }
        Console.WriteLine(" -> null");
    }

    static void Main()
    {
        int[] input = { 2, 4, 6, 8 };
        int[] prefixSum = BuildPrefixSum(input);
        PrintArray(prefixSum);
    }
}

prefixSum[0] = arr[0]; // first prefix sum is first element

initialize prefix sum with first element

prefixSum[i] = prefixSum[i - 1] + arr[i]; // add current element to previous sum

accumulate sum by adding current element to previous prefix sum

Output

2 -> 6 -> 12 -> 20 -> null

Complexity Analysis

Time: O(n) because we go through the array once to build prefix sums

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

vs Alternative: Without prefix sums, summing any subarray takes O(k) time, but prefix sums let us do it in O(1) after O(n) preprocessing

Edge Cases

empty array

returns an empty prefix sum array without error

DSA C#

if (n == 0) return prefixSum; // handle empty array

single element array

prefix sum array is the same single element

DSA C#

prefixSum[0] = arr[0]; // first prefix sum is first element

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 index 1 without initializing index 0
Fix: Always set prefixSum[0] = arr[0] before the loop

Mistake: Adding arr[i] to arr[i-1] instead of prefixSum[i-1]
Fix: Add current element to prefixSum[i-1], not arr[i-1]

Summary

Creates 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 sums of any part of an array multiple times.

The key is to build sums step-by-step so you can subtract to get any sub-sum instantly.

Practice

1. What is the main purpose of a Prefix Sum Array in algorithms?

easy

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

B. To sort the array elements in ascending order

C. To find the maximum element in the array

D. To reverse the array elements

Solution

1. Step 1: Understand what prefix sums represent

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

2. Step 2: Identify the use of prefix sums

   Using prefix sums, we can find the sum of any subarray quickly by subtracting two prefix sums.

3. Final Answer:

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

4. Quick Check:

   Prefix Sum Array = Fast subarray sums [OK]

Hint: Prefix sums help sum subarrays fast by subtraction [OK]

Common Mistakes:

• Thinking prefix sums sort the array
• Confusing prefix sums with maximum element search
• Assuming prefix sums reverse the array

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

easy

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

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

C. int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i

D. int[] prefix = new int[arr.Length]; prefix[0] = 0; for(int i=1; i

Solution

1. Step 1: Check initialization of prefix array

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

2. Step 2: Verify loop for cumulative sum

   The loop starts from 1 and adds prefix[i-1] + arr[i], correctly building prefix sums.

3. Final Answer:

   int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i -> Option C

4. Quick Check:

   Correct prefix sum initialization = int[] prefix = new int[arr.Length]; prefix[0] = arr[0]; for(int i=1; i

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

Common Mistakes:

• Using wrong array length for prefix
• Starting loop from 0 instead of 1
• Accessing arr out of bounds (like arr[i] when i == arr.Length)

3. Given the array arr = new int[] {2, 4, 6, 8} and its prefix sum array prefix computed as usual, what is the output of prefix[3] - prefix[1]?

medium

A. 18

B. 10

C. 12

D. 14

Solution

1. Step 1: Compute prefix sum array

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

2. Step 2: Calculate prefix[3] - prefix[1]

   20 - 6 = 14

3. Final Answer:

   14 -> Option D

4. Quick Check:

   Sum from index 2 to 3 = 6+8 = 14 [OK]

Hint: Subtract prefix sums to get subarray sum [OK]

Common Mistakes:

• Confusing indices and subtracting wrong prefix values
• Adding prefix sums instead of subtracting
• Forgetting prefix sums start at index 0

4. Consider the following code snippet to build a prefix sum array. Identify the error:

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

medium

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

B. prefix[0] should be arr[0], not 0

C. Array prefix should have length arr.Length + 1

D. No error, code is correct

Solution

1. Step 1: Check initialization of prefix[0]

   Setting prefix[0] = 0 is incorrect; it should be arr[0] to start cumulative sum correctly.

2. Step 2: Verify loop and array length

   The loop starting at 1 and array length are fine; only prefix[0] initialization is wrong.

3. Final Answer:

   prefix[0] should be arr[0], not 0 -> Option B

4. Quick Check:

   Correct prefix start = arr[0] [OK]

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

Common Mistakes:

• Starting loop at 0 causing index errors
• Using wrong prefix array size
• Assuming zero initialization is always correct

5. You have an integer array arr of length 6: {3, 1, 4, 1, 5, 9}. You want to find the sum of elements from index 2 to 5 inclusive using a prefix sum array prefix where prefix[i] stores sum of elements from index 0 to i. Which expression correctly computes this sum?

hard

A. prefix[5] - prefix[1]

B. prefix[5] - prefix[2]

C. prefix[4] - prefix[1]

D. prefix[5] + prefix[1]

Solution

1. Step 1: Understand prefix sum indexing

   prefix[i] = sum of arr[0] to arr[i]. To get sum from index 2 to 5, subtract prefix[1] (sum up to index 1) from prefix[5].

2. Step 2: Write the correct expression

   Sum = prefix[5] - prefix[1]

3. Final Answer:

   prefix[5] - prefix[1] -> Option A

4. Quick Check:

   Sum(2 to 5) = prefix[5] - prefix[1] [OK]

Hint: Sum(i to j) = prefix[j] - prefix[i-1] [OK]

Common Mistakes:

• Subtracting prefix[i] instead of prefix[i-1]
• Adding prefix sums instead of subtracting
• Using wrong indices for prefix array