Why Prefix Sum Array in DSA Rust?

The Big Idea

Discover how a simple running total can save you from endless adding and speed up your programs!

The Scenario

Imagine you have a long list of daily sales numbers, and you want to quickly find the total sales between any two days. Doing this by adding each day's sales every time you ask is like counting coins one by one every time you want to know your total money.

The Problem

Manually adding numbers for each query is slow and tiring. If you have many queries, you waste a lot of time repeating the same additions. It is easy to make mistakes, especially with long lists, and the process becomes frustrating.

The Solution

A prefix sum array keeps a running total of sales up to each day. This way, to find the total sales between two days, you just subtract two numbers. It saves time and reduces errors by avoiding repeated addition.

Before vs After

✗ Before

fn sum_range(sales: &[i32], start: usize, end: usize) -> i32 {
    let mut total = 0;
    for i in start..=end {
        total += sales[i];
    }
    total
}

✓ After

fn prefix_sum(sales: &[i32]) -> Vec<i32> {
    let mut prefix = vec![0; sales.len() + 1];
    for i in 0..sales.len() {
        prefix[i + 1] = prefix[i] + sales[i];
    }
    prefix
}

fn sum_range(prefix: &[i32], start: usize, end: usize) -> i32 {
    prefix[end + 1] - prefix[start]
}

What It Enables

This lets you answer sum queries instantly, even on huge lists, making your programs fast and efficient.

Real Life Example

Online stores use prefix sums to quickly calculate total sales between any dates, helping managers see trends without waiting.

Key Takeaways

Manually adding sums repeatedly is slow and error-prone.

Prefix sum arrays store running totals to speed up sum queries.

They make repeated range sum queries fast and simple.

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