Prefix Sum Array in DSA Rust - Execution Trace

Concept Flow - Prefix Sum Array

Start with input array

↓

Initialize prefix_sum array with first element

↓

For each next element i

↓

Calculate prefix_sum[i

↓

Store result in prefix_sum array

↓

Repeat until end of input array

↓

Prefix sum array ready

Build prefix sum by adding each element to sum of all previous elements, storing results step-by-step.

Execution Sample

DSA Rust

let input = [2, 4, 6, 8];
let mut prefix_sum = vec![0; input.len()];
prefix_sum[0] = input[0];
for i in 1..input.len() {
    prefix_sum[i] = prefix_sum[i-1] + input[i];
}
println!("{:?}", prefix_sum);

Calculate prefix sums of input array [2,4,6,8] storing cumulative sums in prefix_sum array.

Execution Table

Step	Operation	Index i	prefix_sum[i]	Calculation	prefix_sum Array State
1	Initialize prefix_sum[0]	0	2	prefix_sum[0] = input[0] = 2	[2, 0, 0, 0]
2	Calculate prefix_sum[1]	1	6	prefix_sum[1] = prefix_sum[0] + input[1] = 2 + 4	[2, 6, 0, 0]
3	Calculate prefix_sum[2]	2	12	prefix_sum[2] = prefix_sum[1] + input[2] = 6 + 6	[2, 6, 12, 0]
4	Calculate prefix_sum[3]	3	20	prefix_sum[3] = prefix_sum[2] + input[3] = 12 + 8	[2, 6, 12, 20]
5	End loop	-	-	All elements processed	[2, 6, 12, 20]

💡 Loop ends after processing all elements of input array

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
i	-	0	1	2	3	-
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]

Key Moments - 3 Insights

Why do we start prefix_sum with the first element of input instead of zero?

Because prefix_sum[0] must represent the sum of elements up to index 0, which is just input[0]. This is shown in execution_table step 1 where prefix_sum[0] = 2.

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

Adding prefix_sum[i-1] accumulates the sum of all previous elements. This is clear in steps 2-4 where prefix_sum[i] builds on prefix_sum[i-1].

What happens if the input array is empty?

The loop does not run and prefix_sum 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 at step 3, what is the value of 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 first contain the value 6?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'prefix_sum Array State' column in execution_table for when 6 appears

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

A 7

B 6

C 5

D 9

💡 Hint

Recall prefix_sum[1] = prefix_sum[0] + input[1], check variable_tracker for prefix_sum[0]

Concept Snapshot

Prefix Sum Array:
- Create array where each element is sum of all previous elements
- prefix_sum[0] = input[0]
- prefix_sum[i] = prefix_sum[i-1] + input[i]
- Useful for quick range sum queries
- Runs in O(n) time
- Requires O(n) extra space

Full Transcript

Prefix Sum Array builds a new array where each position holds the sum of all elements from the start up to that position in the input array. We start by setting prefix_sum[0] equal to input[0]. Then for each next index i, we add input[i] to prefix_sum[i-1] and store it in prefix_sum[i]. This process continues until all elements are processed. The final prefix_sum array allows quick calculation of sums over any range by subtraction. The execution table shows each step updating prefix_sum and the variable tracker records how prefix_sum changes after each step. Key moments clarify why we start with the first element and why accumulation is necessary. The visual quiz tests understanding of values at specific steps and effects of input changes.

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 consecutive elements in arr

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

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

D. An array where each element is the maximum value found 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 up to that index in arr matches this definition exactly, describing cumulative sums.

3. Final Answer:

   An array where each element is the sum of all elements up to that index in arr -> Option C

4. Quick Check:

   Prefix sum = cumulative sum [OK]

Hint: Prefix sum means cumulative sum from start to current index [OK]

Common Mistakes:

• Confusing prefix sum with product or max operations
• Thinking prefix sum stores differences between elements
• Assuming prefix sum stores only the last element's value

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

easy

A. let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; }

B. let mut prefix = vec![0; arr.len()]; for i in 0..arr.len() { prefix[i] = arr[i] + prefix[i+1]; }

C. let prefix = arr.iter().map(|x| *x).collect::();

D. let mut prefix = vec![0; arr.len()]; prefix[0] = 0; for i in 1..arr.len() { prefix[i] = prefix[i-1] * arr[i]; }

Solution

1. Step 1: Check initialization and first element assignment

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } initializes prefix with zeros, sets prefix[0] = arr[0], which is correct.

2. Step 2: Verify loop logic for prefix sums

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } loops from 1 to end, adding prefix[i-1] + arr[i], correctly building prefix sums.

3. Final Answer:

   let mut prefix = vec![0; arr.len()]; prefix[0] = arr[0]; for i in 1..arr.len() { prefix[i] = prefix[i-1] + arr[i]; } -> Option A

4. Quick Check:

   Correct prefix sum loop syntax [OK]

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

Common Mistakes:

• Using prefix[i+1] inside loop causing out-of-bounds
• Multiplying instead of adding elements
• Not initializing prefix[0] before loop

3. Given the Rust code below, what is the printed output?

let arr = vec![2, 4, 6, 8];
let mut prefix = vec![0; arr.len()];
prefix[0] = arr[0];
for i in 1..arr.len() {
    prefix[i] = prefix[i-1] + arr[i];
}
println!("{:?}", prefix);

medium

A. [2, 8, 14, 22]

B. [2, 4, 6, 8]

C. [0, 2, 6, 12]

D. [2, 6, 12, 20]

Solution

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

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

2. Step 2: Confirm final prefix array

   The prefix array is [2, 6, 12, 20], matching [2, 6, 12, 20].

3. Final Answer:

   [2, 6, 12, 20] -> Option D

4. Quick Check:

   Sum accumulates correctly [OK]

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

Common Mistakes:

• Printing original array instead of prefix
• Starting prefix sums from zero incorrectly
• Miscomputing sums by skipping elements

4. Identify the error in the following Rust code that attempts to create a prefix sum array and fix it:

let arr = vec![1, 3, 5];
let mut prefix = vec![0; arr.len()];
for i in 0..arr.len() {
    prefix[i] = prefix[i-1] + arr[i];
}
println!("{:?}", prefix);

medium

A. The loop starts at 0 but uses prefix[i-1], causing out-of-bounds; start loop at 1 and set prefix[0] = arr[0]

B. The vector prefix is not mutable; add mut keyword

C. The arr vector is empty; initialize with values

D. The println! macro is missing a semicolon

Solution

1. Step 1: Identify cause of out-of-bounds error

   At i=0, prefix[i-1] is prefix[-1], which is invalid in Rust and causes panic.

2. Step 2: Fix loop and initialization

   Set prefix[0] = arr[0] before loop, then loop from i=1 to arr.len()-1 to safely access prefix[i-1].

3. Final Answer:

   The loop starts at 0 but uses prefix[i-1], causing out-of-bounds; start loop at 1 and set prefix[0] = arr[0] -> Option A

4. Quick Check:

   Indexing prefix[i-1] at i=0 causes error [OK]

Hint: Avoid negative indexing; initialize first element before loop [OK]

Common Mistakes:

• Starting loop at 0 and accessing prefix[i-1]
• Not initializing prefix[0] before loop
• Ignoring Rust's strict bounds checking

5. You have an array arr = [3, 1, 4, 1, 5, 9, 2]. Using a prefix sum array, how would you efficiently find the sum of elements between indices 2 and 5 (inclusive)?

hard

A. Calculate prefix sums, then sum = prefix[5] + prefix[2]

B. Calculate prefix sums, then sum = prefix[5] - prefix[1]

C. Calculate prefix sums, then sum = prefix[5] - prefix[2]

D. Calculate prefix sums, then sum = prefix[6] - prefix[2]

Solution

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

   Sum from index l to r = prefix[r] - prefix[l-1], assuming prefix sums start at index 0.

2. Step 2: Apply to given indices 2 to 5

   Sum = prefix[5] - prefix[1], since prefix[1] is sum up to index 1.

3. Final Answer:

   Calculate prefix sums, then sum = prefix[5] - prefix[1] -> Option B

4. Quick Check:

   Range sum = prefix[r] - prefix[l-1] [OK]

Hint: Range sum = prefix[end] - prefix[start-1] [OK]

Common Mistakes:

• Subtracting prefix[start] instead of prefix[start-1]
• Adding prefix values instead of subtracting
• Using wrong indices for prefix subtraction