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 i from 1 to n-1

↓

Calculate prefix[i

↓

Repeat until end

↓

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[4];
prefix[0] = arr[0];
for(int i=1; i<4; 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]	Visual 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	4	N/A	N/A	N/A	[2, 6, 12, 20]

💡 Loop ends as i reaches array length 4, no more elements to process.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	undefined	0	1	2	3	4
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 to add subsequent elements to this initial sum, as shown in execution_table step 1.

What happens if the original array is empty?

The loop does not run and prefix array remains empty. This is because the exit condition in execution_table step 5 stops immediately when array length is zero.

Why do we use prefix[i-1] inside the loop?

prefix[i-1] holds the sum of all elements before index i. Adding arr[i] to it gives the sum up to index i, as seen in execution_table steps 2 to 4.

Visual Quiz - 3 Questions

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

A 8

B 6

C 12

D 20

💡 Hint

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

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

A Step 3

B Step 4

C Step 5

D Step 2

💡 Hint

Look at the Visual State column; full array is complete at step 4.

If arr[1] 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 where each element is the sum of all elements up to that index.
- prefix[0] = arr[0]
- For i>0: prefix[i] = prefix[i-1] + arr[i]
- Useful for fast range sum queries.
- Time complexity: O(n) to build.

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 array 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. The execution table shows each step of this process, tracking the index, values added, and the resulting prefix array state.

Practice

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

easy

A. An array where each element is the difference between the current and previous element in arr

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

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

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

Solution

1. Step 1: Understand prefix sum array definition

   A prefix sum array stores cumulative sums, where each element at index i is the sum of all elements from index 0 to i in the original array.

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 cumulative sum property. Other options 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 C

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 resets at each index

2. Which of the following C++ code snippets correctly initializes a prefix sum array prefix from an integer array arr of size n?

easy

A. prefix[0] = 0; for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + arr[i];

B. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i];

C. prefix[0] = arr[0]; for(int i = 0; i < n; i++) prefix[i] = prefix[i-1] + arr[i];

D. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = arr[i] - prefix[i-1];

Solution

1. Step 1: Check initialization of prefix array

   Prefix sum starts with prefix[0] = arr[0], which is correct in options B, C, and D.

2. Step 2: Verify loop and summation logic

   prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; correctly loops from i=1 to n-1 and adds prefix[i-1] + arr[i]. prefix[0] = 0; for(int i = 1; i <= n; i++) prefix[i] = prefix[i-1] + arr[i]; has wrong indexing and loop range. prefix[0] = arr[0]; for(int i = 0; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; uses prefix[i-1] at i=0 which is invalid. prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = arr[i] - prefix[i-1]; subtracts instead of adding.

3. Final Answer:

   prefix[0] = arr[0]; for(int i = 1; i < n; i++) prefix[i] = prefix[i-1] + arr[i]; -> Option B

4. Quick Check:

   Initialize first, then add previous prefix + current [OK]

Hint: Start prefix[0] = arr[0], then add previous prefix + current [OK]

Common Mistakes:

• Starting loop at 0 and accessing prefix[-1]
• Using wrong loop bounds (<= n instead of < n)
• Subtracting instead of adding elements

3. What is the output of the following C++ code?

int arr[] = {2, 4, 6, 8};
int n = 4;
int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i < n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}
for(int i = 0; i < n; i++) {
    std::cout << prefix[i] << " ";
}

medium

A. 2 6 12 20

B. 2 4 6 8

C. 2 8 14 20

D. 2 6 10 18

Solution

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

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

2. Step 2: Print prefix array elements

   Output is: 2 6 12 20

3. Final Answer:

   2 6 12 20 -> Option A

4. Quick Check:

   Sum accumulates: 2, 6, 12, 20 [OK]

Hint: Add current element to previous prefix sum each step [OK]

Common Mistakes:

• Printing original array instead of prefix sums
• Incorrect addition order
• Off-by-one errors in loop

4. Identify the error in the following prefix sum array code and select the corrected version:

int arr[] = {1, 3, 5, 7};
int n = 4;
int prefix[4];
prefix[0] = arr[0];
for(int i = 1; i <= n; i++) {
    prefix[i] = prefix[i-1] + arr[i];
}

medium

A. Change loop condition to i < n to avoid out-of-bounds access

B. Initialize prefix[0] = 0 instead of arr[0]

C. Use i = 0 as loop start and keep condition i < n

D. Replace prefix[i] with arr[i] inside loop

Solution

1. Step 1: Analyze loop bounds and array indexing

   The loop runs with i from 1 to n inclusive (i <= n). Since arrays are 0-indexed, prefix[n] and arr[n] access out-of-bounds elements causing runtime error.

2. Step 2: Correct loop condition

   Changing loop condition to i < n ensures indices stay within valid range (0 to n-1).

3. Final Answer:

   Change loop condition to i < n to avoid out-of-bounds access -> Option A

4. Quick Check:

   Loop must stay within array size [OK]

Hint: Loop index must be less than array size, not less or equal [OK]

Common Mistakes:

• Using <= n causing out-of-bounds errors
• Starting loop at 0 and accessing prefix[-1]
• Incorrect initialization of prefix[0]

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

hard

A. Sum = prefix[r] / prefix[l-1] if l > 0, else prefix[r]

B. Sum = prefix[r] + prefix[l-1] if l > 0, else prefix[r]

C. Sum = prefix[r] * prefix[l-1] if l > 0, else prefix[r]

D. Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r]

Solution

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

   Prefix sum at index r gives sum from 0 to r. To get sum from l to r, subtract sum from 0 to l-1, which is prefix[l-1]. If l is 0, sum is prefix[r].

2. Step 2: Apply formula for sum between l and r

   Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r]. Other operations like addition, multiplication, or division are incorrect.

3. Final Answer:

   Sum = prefix[r] - prefix[l-1] if l > 0, else prefix[r] -> Option D

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[l-1] instead of subtracting
• Using multiplication or division incorrectly
• Not handling case when l = 0