Prefix Sum Array in DSA C - 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

We start with the original array, then build a new array where each element is the sum of all elements up to that index.

Execution Sample

DSA C

int arr[] = {2, 4, 6, 8};
int prefix_sum[4];
prefix_sum[0] = arr[0];
for(int i=1; i<4; i++) {
  prefix_sum[i] = prefix_sum[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_sum[i]	Calculation	Prefix Sum Array State
1	Initialize prefix_sum[0]	0	2	prefix_sum[0] = arr[0] = 2	[2, _, _, _]
2	Calculate prefix_sum[1]	1	6	prefix_sum[1] = prefix_sum[0] + arr[1] = 2 + 4	[2, 6, _, _]
3	Calculate prefix_sum[2]	2	12	prefix_sum[2] = prefix_sum[1] + arr[2] = 6 + 6	[2, 6, 12, _]
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

💡 Loop ends after i reaches 3 (last index), prefix sum array fully computed

Variable Tracker

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

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 shift all sums by one and cause incorrect results. See Step 1 in execution_table.

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, which is stored in prefix_sum[i-1]. Adding arr[i] extends the sum to include the current element. See Steps 2-4 in execution_table.

What happens if the original array is empty?

The loop does not run and prefix_sum remains empty. No prefix sums can be computed. This is why initialization and loop conditions are important.

Visual Quiz - 3 Questions

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

A 20

B 6

C 12

D 8

💡 Hint

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

At which step does the prefix_sum array become fully computed?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

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

If the original array was {1, 1, 1, 1}, what would prefix_sum[3] be?

A 3

B 4

C 1

D 0

💡 Hint

Sum all elements up to index 3: 1+1+1+1

Concept Snapshot

Prefix Sum Array:
- prefix_sum[0] = arr[0]
- prefix_sum[i] = prefix_sum[i-1] + arr[i]
- Each element stores sum of all previous elements
- Useful for quick range sum queries
- Runs in O(n) time

Full Transcript

The prefix sum array is built by starting with the first element of the original array. Then, for each next element, we add it to the sum of all previous elements stored in the prefix sum array. This way, each position in the prefix sum array holds the total sum from the start up to that index. The process stops when all elements are processed. This helps quickly find sums of any subarray later.