Prefix Sum Array in DSA Rust

Mental Model

A prefix sum array stores the sum of all elements up to each position, so you can quickly find sums of parts of the array.

Analogy: Imagine a row of buckets where each bucket holds the total water collected from the first bucket up to that bucket. To find water between any two buckets, you just subtract the amounts in those buckets.

Original array: [2, 4, 6, 8]
Prefix sum:    [2, 6, 12, 20]
Index:          0   1    2    3

Dry Run Walkthrough

Input: array: [2, 4, 6, 8]

Goal: Create a prefix sum array to quickly find sums of any subarray

Step 1: Start with first element as prefix sum

Prefix sum: [2, _, _, _]

Why: The first prefix sum is just the first element itself

Step 2: Add second element to previous prefix sum

Prefix sum: [2, 6, _, _]

Why: Sum of first two elements is 2 + 4 = 6

Step 3: Add third element to previous prefix sum

Prefix sum: [2, 6, 12, _]

Why: Sum of first three elements is 6 + 6 = 12

Step 4: Add fourth element to previous prefix sum

Prefix sum: [2, 6, 12, 20]

Why: Sum of all four elements is 12 + 8 = 20

Result:

Prefix sum array: [2, 6, 12, 20]

Annotated Code

DSA Rust

fn prefix_sum_array(arr: &[i32]) -> Vec<i32> {
    let mut prefix_sums = Vec::with_capacity(arr.len());
    if arr.is_empty() {
        return prefix_sums;
    }
    prefix_sums.push(arr[0]); // start with first element
    for i in 1..arr.len() {
        // add current element to last prefix sum
        let sum = prefix_sums[i - 1] + arr[i];
        prefix_sums.push(sum);
    }
    prefix_sums
}

fn main() {
    let arr = [2, 4, 6, 8];
    let prefix_sums = prefix_sum_array(&arr);
    println!("Prefix sum array: {:?}", prefix_sums);
}

prefix_sums.push(arr[0]); // start with first element

initialize prefix sum with first element

let sum = prefix_sums[i - 1] + arr[i];

add current element to previous prefix sum to get new prefix sum

prefix_sums.push(sum);

store new prefix sum in the array

Output

Prefix sum array: [2, 6, 12, 20]

Complexity Analysis

Time: O(n) because we process each element once to build the prefix sums

Space: O(n) because we store a prefix sum for each element in the array

vs Alternative: Without prefix sums, summing any subarray takes O(k) time, but with prefix sums it takes O(1) after O(n) preprocessing

Edge Cases

empty array

returns an empty prefix sum array

DSA Rust

if arr.is_empty() { return prefix_sums; }

single element array

prefix sum array contains just that element

DSA Rust

prefix_sums.push(arr[0]);

When to Use This Pattern

When you need to find sums of many subarrays quickly, use prefix sum arrays to reduce repeated addition.

Common Mistakes

Mistake: Starting prefix sums with zero instead of the first element
Fix: Initialize prefix sums with the first element of the array to avoid off-by-one errors

Mistake: Adding current element to the current prefix sum instead of the previous prefix sum
Fix: Always add the current element to the last prefix sum value, not the current one

Summary

It creates an array where each position holds the sum of all elements up to that position.

Use it when you want to quickly find the sum of any part of an array multiple times.

The key is to build sums step-by-step so you can subtract to get any sub-sum instantly.

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