Prefix Sum Array in DSA Go - Execution Trace

Concept Flow - Prefix Sum Array

Start with input array

↓

Create prefix sum array of same size

↓

Set prefix[0

↓

For each i from 1 to end

↓

Calculate prefix[i

↓

Prefix sum array ready

↓

Use prefix sums for fast range 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 Go

input := []int{2, 4, 6, 8}
prefix := make([]int, len(input))
prefix[0] = input[0]
for i := 1; i < len(input); i++ {
    prefix[i] = prefix[i-1] + input[i]
}

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

Execution Table

Step	Operation	Index i	prefix[i-1]	input[i]	prefix[i]	Prefix Sum 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 processing all elements; prefix sum array fully computed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
prefix	[_, _, _, _]	[2, _, _, _]	[2, 6, _, _]	[2, 6, 12, _]	[2, 6, 12, 20]	[2, 6, 12, 20]
i	N/A	0	1	2	3	End

Key Moments - 3 Insights

Why do we start prefix[0] with input[0] instead of 0?

Because prefix[0] represents the sum of elements up to index 0, which is just input[0]. This is shown in execution_table step 1 where prefix[0] is set to 2.

Why do we add prefix[i-1] to input[i] instead of just input[i]?

Adding prefix[i-1] accumulates the sum of all previous elements, so prefix[i] holds the total sum up to index i. See execution_table steps 2-4 where prefix[i] is calculated by adding prefix[i-1] and input[i].

What happens if the input array is empty?

The loop does not run and prefix sum array remains empty. This is implied by the exit_note where loop ends after processing all elements.

Visual Quiz - 3 Questions

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

A 6

B 12

C 8

D 20

💡 Hint

Check the 'prefix[i]' column in row with Step 3.

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

A Step 4

B Step 3

C Step 5

D Step 2

💡 Hint

Look at the 'Prefix Sum Array State' column to see when all elements are filled.

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

A 6

B 5

C 7

D 9

💡 Hint

prefix[1] = prefix[0] + input[1], check prefix[0] and new input[1] values.

Concept Snapshot

Prefix Sum Array:
- Create array prefix same size as input
- prefix[0] = input[0]
- For i=1 to end: prefix[i] = prefix[i-1] + input[i]
- prefix[i] holds sum of input[0..i]
- Enables fast range sum queries

Full Transcript

This visualization shows how to build a prefix sum array from an input array. We start by setting prefix[0] equal to input[0]. Then for each index i from 1 to the end, we add the previous prefix sum prefix[i-1] to the current input element input[i] to get prefix[i]. This way, prefix[i] stores the sum of all elements from the start up to index i. The execution table traces each step, showing how the prefix array fills up. Key moments clarify why we start with prefix[0] = input[0] and why we add prefix[i-1] to input[i]. The quiz tests understanding of the prefix sums at different steps and how changes in input affect the prefix array.

Practice

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

easy

A. To find the maximum element in the array

B. To sort the array elements in ascending order

C. To reverse the array elements efficiently

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

Solution

1. Step 1: Understand prefix sum array concept

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

2. Step 2: Use prefix sums for subarray sums

   Using prefix sums, sum of any subarray can be found quickly by subtracting two prefix sums.

3. Final Answer:

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

4. Quick Check:

   Prefix sum array helps fast subarray sums [OK]

Hint: Prefix sums store cumulative sums for fast subarray queries [OK]

Common Mistakes:

• Confusing prefix sum with sorting
• Thinking prefix sum reverses array
• Assuming prefix sum finds max element

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

easy

A. prefix := make([]int, len(arr))
for i := 0; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

B. prefix := make([]int, len(arr)+1)
for i := 1; i <= len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i-1]
}

C. prefix := make([]int, len(arr)+1)
for i := 0; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

D. prefix := make([]int, len(arr))
for i := 1; i < len(arr); i++ {
prefix[i] = prefix[i-1] + arr[i]
}

Solution

1. Step 1: Check prefix array size and indexing

   Prefix sum array usually has length one more than original to handle zero prefix sum at start.

2. Step 2: Verify loop and indexing logic

   Loop from 1 to len(arr), prefix[i] = prefix[i-1] + arr[i-1] correctly accumulates sums.

3. Final Answer:

   prefix := make([]int, len(arr)+1) for i := 1; i <= len(arr); i++ { prefix[i] = prefix[i-1] + arr[i-1] } -> Option B

4. Quick Check:

   Correct prefix sum initialization uses offset indexing [OK]

Hint: Prefix array length = original length + 1, loop starts at 1 [OK]

Common Mistakes:

• Using prefix array same length as original
• Starting loop at 0 and accessing prefix[-1]
• Incorrect indexing of arr inside loop

3. What is the output of the following Go code?

arr := []int{2, 4, 6, 8}
prefix := make([]int, len(arr)+1)
for i := 1; i <= len(arr); i++ {
  prefix[i] = prefix[i-1] + arr[i-1]
}
fmt.Println(prefix)

medium

A. [0 2 6 12 20]

B. [2 6 12 20 28]

C. [0 2 4 6 8]

D. [2 4 6 8 0]

Solution

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

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

2. Step 2: Write final prefix array

   The prefix array is [0, 2, 6, 12, 20]

3. Final Answer:

   [0 2 6 12 20] -> Option A

4. Quick Check:

   Sum accumulates correctly in prefix array [OK]

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

Common Mistakes:

• Forgetting initial zero in prefix array
• Adding wrong elements at each step
• Confusing prefix array length

4. Identify the error in this Go code that tries to build a prefix sum array:

arr := []int{1, 3, 5}
prefix := make([]int, len(arr))
for i := 1; i < len(arr); i++ {
  prefix[i] = prefix[i-1] + arr[i]
}
fmt.Println(prefix)

medium

A. prefix array size should be len(arr)+1

B. Loop should start from i=0 instead of i=1

C. prefix[0] is not initialized before use

D. arr indexing is out of range

Solution

1. Step 1: Check prefix array initialization

   Prefix array is size len(arr), which can work but prefix[0] must be set before use.

2. Step 2: Analyze loop and prefix[0]

   Loop starts at i=1, prefix[1] = prefix[0] + arr[1]. prefix[0] is zero by default in Go, but it should be explicitly set to arr[0] before the loop.

3. Step 3: Check correctness of prefix sums

   prefix[0] is zero, but arr[0] is never added, so prefix sums are incomplete.

4. Final Answer:

   prefix[0] is not initialized before use -> Option C

5. Quick Check:

   Missing prefix[0] initialization causes wrong sums [OK]

Hint: Initialize prefix[0] before loop to avoid wrong sums [OK]

Common Mistakes:

• Not initializing prefix[0]
• Wrong prefix array size
• Incorrect loop start index

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

hard

A. sum = prefix[r+1] - prefix[l]

B. sum = prefix[r] - prefix[l-1]

C. sum = prefix[r] + prefix[l]

D. sum = prefix[r+1] + prefix[l-1]

Solution

1. Step 1: Understand prefix sum indexing

   Prefix sum array usually has length len(arr)+1 with prefix[0]=0, prefix[i] = sum of arr[0..i-1].

2. Step 2: Calculate subarray sum using prefix sums

   Sum from l to r = prefix[r+1] - prefix[l] because prefix[r+1] sums up to arr[r].

3. Final Answer:

   sum = prefix[r+1] - prefix[l] -> Option A

4. Quick Check:

   Subarray sum = prefix[r+1] - prefix[l] [OK]

Hint: Use prefix[r+1] - prefix[l] for sum between l and r [OK]

Common Mistakes:

• Using prefix[r] - prefix[l-1] without offset
• Adding prefix sums instead of subtracting
• Confusing indices by 1