Prefix Sum Array in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Prefix Sum Array?

A Prefix Sum Array is a new array where each element at index i is the sum of all elements from the start up to index i in the original array. It helps to quickly find the sum of any subarray.

beginner

How do you compute a Prefix Sum Array from an input array?

Start with the first element as it is. Then for each next element, add it to the sum of all previous elements stored in the prefix sum array at the previous index.

beginner

What is the time complexity of building a Prefix Sum Array for an array of size n?

The time complexity is O(n) because you visit each element once to compute the prefix sums.

intermediate

How can a Prefix Sum Array help in finding the sum of elements between two indices i and j quickly?

You can find the sum between i and j by subtracting prefix_sum[i-1] from prefix_sum[j]. This gives the sum of elements from i to j in O(1) time.

beginner

Show a simple Rust code snippet to create a Prefix Sum Array from a vector of integers.

fn prefix_sum(arr: &Vec<i32>) -> Vec<i32> {
    let mut prefix = Vec::with_capacity(arr.len());
    let mut sum = 0;
    for &num in arr.iter() {
        sum += num;
        prefix.push(sum);
    }
    prefix
}

What does the element at index i in a prefix sum array represent?

A Product of elements from index 0 to i in the original array

B Value of the element at index i in the original array

C Sum of elements from index 0 to i in the original array

D Difference between elements at index i and i-1

Each element at index i in the prefix sum array stores the sum of all elements from the start up to index i in the original array.

What is the time complexity to find the sum of elements between two indices i and j using a prefix sum array?

A O(1)

B O(n)

C O(log n)

D O(j - i)

Using a prefix sum array, the sum between two indices can be found in constant time by subtracting prefix_sum[i-1] from prefix_sum[j].

Which of the following is NOT a benefit of using a prefix sum array?

A Fast range sum queries

B Fast updates to individual elements

C Simple to build in O(n) time

D Reduces repeated summation calculations

Prefix sum arrays do not support fast updates to individual elements; updating requires rebuilding or advanced data structures.

If the original array is [3, 1, 4, 1, 5], what is the prefix sum array?

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

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

C [3, 3, 3, 3, 3]

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

Prefix sums are cumulative sums: 3, 3+1=4, 4+4=8, 8+1=9, 9+5=14.

In Rust, which method is best to iterate over elements when building a prefix sum array?

A Using map() without collecting

B Using while loop with indexing

C Using recursion

D Using iter() with a for loop

Using iter() with a for loop is simple and efficient for traversing elements to build prefix sums.

Explain how a prefix sum array is constructed and how it helps in answering range sum queries.

Think about adding elements cumulatively and subtracting sums to get ranges.

Write a simple Rust function to create a prefix sum array from a vector of integers and explain each step.

Focus on how the sum accumulates and is stored.

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