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.