Prefix Sum Array in DSA C# - Execution Trace

Concept Flow - Prefix Sum Array

Start with original array

↓

Create prefix sum array of same size

↓

Set prefix[0

↓

For each index i from 1 to end

↓

Calculate prefix[i

↓

Prefix sum array ready for queries

Build a new array where each element is the sum of all elements up to that index in the original array.

Execution Sample

DSA C#

int[] arr = {2, 4, 6, 8};
int[] prefix = new int[arr.Length];
if (arr.Length > 0) {
    prefix[0] = arr[0];
    for (int i = 1; i < arr.Length; i++) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
}

This code creates a prefix sum array from the original array by adding each element to the sum of all previous elements.

Execution Table

Step	Operation	Index i	prefix[i-1]	arr[i]	prefix[i]	Prefix Array State
1	Initialize prefix[0]	0	N/A	2	2	[2, _, _, _]
2	Calculate prefix[1]	1	2	4	6	[2, 6, _, _]
3	Calculate prefix[2]	2	6	6	12	[2, 6, 12, _]
4	Calculate prefix[3]	3	12	8	20	[2, 6, 12, 20]
5	End loop	N/A	N/A	N/A	N/A	[2, 6, 12, 20]

💡 Loop ends after i reaches arr.Length (4), prefix sum array fully computed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	N/A	0	1	2	3	4 (loop ends)
prefix[0]	undefined	2	2	2	2	2
prefix[1]	undefined	undefined	6	6	6	6
prefix[2]	undefined	undefined	undefined	12	12	12
prefix[3]	undefined	undefined	undefined	undefined	20	20

Key Moments - 3 Insights

Why do we set prefix[0] = arr[0] before the loop?

Because prefix[0] is the sum of the first element only. The loop starts from i=1, so we must initialize prefix[0] first as shown in execution_table step 1.

What happens if the original array is empty?

The loop never runs and prefix array remains empty. This is why the exit note in execution_table says the loop ends when i reaches arr.Length.

Why do we add prefix[i-1] and arr[i] to get prefix[i]?

Because prefix[i-1] holds the sum of all elements before index i, adding arr[i] extends the sum to include the current element, as shown in steps 2 to 4 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is prefix[2] after step 3?

A 6

B 20

C 12

D 2

💡 Hint

Check the 'prefix[i]' column in execution_table row for step 3.

At which step does the prefix sum array become fully computed?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Prefix Array State' column and the exit_note in execution_table.

If arr[1] was changed from 4 to 5, what would prefix[1] be after step 2?

A 7

B 6

C 5

D 9

💡 Hint

prefix[1] = prefix[0] + arr[1], check variable_tracker for prefix[0] and arr[1].

Concept Snapshot

Prefix Sum Array:
- Create a new array same size as original.
- prefix[0] = arr[0]
- For i=1 to end: prefix[i] = prefix[i-1] + arr[i]
- Each prefix[i] stores sum of arr[0..i]
- Useful for fast range sum queries.

Full Transcript

The prefix sum array is built by creating a new array where each element at index i is the sum of all elements from the original array up to i. We start by setting prefix[0] equal to arr[0]. Then, for each index from 1 to the end, we add the current original element to the previous prefix sum. This process continues until the entire prefix sum array is computed. This allows quick calculation of sums over any range in the original array.

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