Prefix Sum Array in DSA Python - Execution Trace

Concept Flow - Prefix Sum Array

Start with original array

↓

Initialize prefix_sum array with first element

↓

For each next element i

↓

Calculate prefix_sum[i

↓

Repeat until end of array

↓

Prefix sum array ready for queries

Build prefix sum array by adding each element to sum of all previous elements step-by-step.

Execution Sample

DSA Python

arr = [2, 4, 6, 8]
prefix_sum = [0]*len(arr)
if len(arr) > 0:
    prefix_sum[0] = arr[0]
for i in range(1, len(arr)):
    prefix_sum[i] = prefix_sum[i-1] + arr[i]
print(prefix_sum)

Calculate prefix sums for array [2,4,6,8] step-by-step.

Execution Table

Step	Operation	Index i	prefix_sum[i]	Calculation	Prefix Sum Array State
1	Initialize prefix_sum[0]	0	2	prefix_sum[0] = arr[0] = 2	[2, 0, 0, 0]
2	Calculate prefix_sum[1]	1	6	prefix_sum[1] = prefix_sum[0] + arr[1] = 2 + 4	[2, 6, 0, 0]
3	Calculate prefix_sum[2]	2	12	prefix_sum[2] = prefix_sum[1] + arr[2] = 6 + 6	[2, 6, 12, 0]
4	Calculate prefix_sum[3]	3	20	prefix_sum[3] = prefix_sum[2] + arr[3] = 12 + 8	[2, 6, 12, 20]
5	End loop	-	-	-	Prefix sum array complete

💡 Reached end of array, prefix sum array fully computed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
prefix_sum	[0, 0, 0, 0]	[2, 0, 0, 0]	[2, 6, 0, 0]	[2, 6, 12, 0]	[2, 6, 12, 20]	[2, 6, 12, 20]
i	-	-	1	2	3	-

Key Moments - 3 Insights

Why do we start prefix_sum with prefix_sum[0] = arr[0] instead of 0?

Because prefix_sum[0] represents the sum of the first element only. Starting at 0 would incorrectly represent an empty sum. See execution_table Step 1.

Why do we add prefix_sum[i-1] to arr[i] instead of just arr[i]?

Because prefix_sum[i] must include the sum of all elements before i plus the current element. Adding only arr[i] would ignore previous sums. See execution_table Steps 2-4.

What happens if the original array is empty?

The loop does not run and prefix_sum remains empty. No sums are computed. This is why we check array length before starting. See exit_note.

Visual Quiz - 3 Questions

Look at the execution_table, what is prefix_sum[2] after Step 3?

A 6

B 12

C 8

D 20

💡 Hint

Check the 'prefix_sum[i]' column at Step 3 in execution_table.

At which step does the prefix_sum array first contain the value 20?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Prefix Sum Array State' column for when 20 appears.

If arr was [1, 3, 5], what would prefix_sum[1] be after calculation?

A 1

B 3

C 4

D 5

💡 Hint

prefix_sum[1] = prefix_sum[0] + arr[1], see variable_tracker for similar pattern.

Concept Snapshot

Prefix Sum Array:
- prefix_sum[0] = arr[0]
- prefix_sum[i] = prefix_sum[i-1] + arr[i]
- Builds cumulative sums for quick range queries
- Runs in O(n) time
- Useful for sum queries without repeated addition

Full Transcript

This visual trace shows how to build a prefix sum array from an original array. We start by setting prefix_sum[0] equal to the first element of the original array. Then, for each next index i, we add the current element arr[i] to the sum stored at prefix_sum[i-1]. This way, prefix_sum[i] holds the sum of all elements from index 0 up to i. The execution table tracks each step, showing how the prefix_sum array grows. Key moments clarify why we start with prefix_sum[0] = arr[0] and why we add prefix_sum[i-1] to arr[i]. The quiz tests understanding of these steps and values. This method helps answer sum queries quickly by using precomputed sums.

Practice

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

easy

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

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

C. An array where each element is the difference between consecutive elements in arr.

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

Solution

1. Step 1: Understand prefix sum definition

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

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 sum accumulation; others 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 D

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 stores original array values

2. Which of the following Python code snippets correctly initializes a prefix sum array prefix for an input list arr?

easy

A. prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(arr[i] - prefix[i-1])

B. prefix = []
for i in range(len(arr)):
prefix.append(arr[i] + arr[i-1])

C. prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[i-1] + arr[i])

D. prefix = [0] * len(arr)
for i in range(len(arr)):
prefix[i] = arr[i] * prefix[i-1]

Solution

1. Step 1: Analyze code for prefix sum logic

   prefix = [arr[0]] for i in range(1, len(arr)): prefix.append(prefix[i-1] + arr[i]) starts prefix with first element and adds current element to previous prefix sum correctly.

2. Step 2: Check other options for errors

   prefix = [] for i in range(len(arr)): prefix.append(arr[i] + arr[i-1]) adds current and previous array elements incorrectly; C multiplies instead of sums; A subtracts instead of sums.

3. Final Answer:

   prefix = [arr[0]]\nfor i in range(1, len(arr)):\n prefix.append(prefix[i-1] + arr[i]) -> Option C

4. Quick Check:

   Prefix sum uses cumulative addition [OK]

Hint: Start prefix with first element, then add previous prefix sum [OK]

Common Mistakes:

• Using multiplication instead of addition
• Adding wrong elements or indices
• Initializing prefix array incorrectly

3. What is the output of the following code?

arr = [3, 1, 4, 1, 5]
prefix = [arr[0]]
for i in range(1, len(arr)):
    prefix.append(prefix[i-1] + arr[i])
print(prefix)

medium

A. [3, 4, 8, 9, 14]

B. [3, 1, 4, 1, 5]

C. [3, 3, 7, 8, 13]

D. [0, 3, 4, 8, 9]

Solution

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

   Start with prefix = [3]. Then add 1: 3+1=4, add 4: 4+4=8, add 1: 8+1=9, add 5: 9+5=14.

2. Step 2: Form the final prefix array

   prefix = [3, 4, 8, 9, 14]

3. Final Answer:

   [3, 4, 8, 9, 14] -> Option A

4. Quick Check:

   Sum accumulates correctly [OK]

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

Common Mistakes:

• Confusing prefix array with original array
• Off-by-one errors in indexing
• Incorrect initial prefix value

4. Find the error in this prefix sum code and choose the corrected version:

arr = [2, 4, 6]
prefix = [0]
for i in range(len(arr)):
    prefix.append(prefix[i] + arr[i])
print(prefix)

medium

A. Change prefix = [0] to prefix = [arr[0]] and loop from 1 to len(arr)-1.

B. Change prefix.append(prefix[i] + arr[i]) to prefix.append(prefix[i-1] + arr[i]).

C. Remove the initial zero from prefix and start loop from 0 as is.

D. No error; code works correctly and prints prefix sums.

Solution

1. Step 1: Identify initialization and loop issues

   Initializing prefix with [0] and looping from 0 adds an extra leading zero. Tracing: i=0 append(0+2)=2 -> [0,2]; i=1 append(2+4)=6 -> [0,2,6]; i=2 append(6+6)=12 -> [0,2,6,12]. This produces prefix sums of length n+1 with prefix[0]=0, whereas standard is length n starting from arr[0].

2. Step 2: Correct initialization and loop range

   Start prefix with first element arr[0], then loop from index 1 to end to add sums correctly.

3. Final Answer:

   Change prefix = [0] to prefix = [arr[0]] and loop from 1 to len(arr)-1. -> Option A

4. Quick Check:

   Proper start and loop fix prefix sums [OK]

Hint: Initialize prefix with first element, loop from second element [OK]

Common Mistakes:

• Starting prefix with zero instead of first element
• Looping from zero causing off-by-one errors
• Using wrong prefix index inside loop

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

hard

A. Calculate sum as prefix[r] * prefix[l].

B. Calculate sum as prefix[r] - prefix[l-1] if l > 0, else prefix[r].

C. Calculate sum as prefix[r] + prefix[l] always.

D. Calculate sum by looping from l to r and adding elements.

Solution

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

   Prefix sum at index r stores sum from start to r. To get sum from l to r, subtract sum from start to l-1.

2. Step 2: Handle edge case when l is zero

   If l is zero, sum is prefix[r] directly since no subtraction needed.

3. Final Answer:

   Calculate sum as prefix[r] - prefix[l-1] if l > 0, else prefix[r]. -> Option B

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 sums instead of subtracting
• Ignoring edge case when l = 0
• Using multiplication or looping unnecessarily