Prefix Sum Array in DSA Python

Mental Model

A prefix sum array stores sums of elements from the start up to each position, so we can quickly find sums of any part of the original 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 two buckets, just subtract the totals.

Original array:  [2] -> [4] -> [6] -> [8] -> [10]
Prefix sums:     [2] -> [6] -> [12] -> [20] -> [30]

Dry Run Walkthrough

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

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

Step 1: Start prefix sum with first element same as original

Prefix sums: [2] -> null

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

Step 2: Add second element to previous prefix sum: 2 + 4 = 6

Prefix sums: [2] -> [6] -> null

Why: Each prefix sum adds current element to sum before it

Step 3: Add third element to previous prefix sum: 6 + 6 = 12

Prefix sums: [2] -> [6] -> [12] -> null

Why: Continue accumulating sums step by step

Step 4: Add fourth element to previous prefix sum: 12 + 8 = 20

Prefix sums: [2] -> [6] -> [12] -> [20] -> null

Why: Keep building the prefix sums array

Step 5: Add fifth element to previous prefix sum: 20 + 10 = 30

Prefix sums: [2] -> [6] -> [12] -> [20] -> [30] -> null

Why: Final prefix sum includes all elements

Result:

Prefix sums: [2] -> [6] -> [12] -> [20] -> [30] -> null

Annotated Code

DSA Python

class PrefixSumArray:
    def __init__(self, arr):
        self.arr = arr
        self.prefix_sums = []
        self.build_prefix_sums()

    def build_prefix_sums(self):
        if not self.arr:
            return
        self.prefix_sums.append(self.arr[0])  # start with first element
        for i in range(1, len(self.arr)):
            # add current element to last prefix sum
            self.prefix_sums.append(self.prefix_sums[i-1] + self.arr[i])

    def range_sum(self, left, right):
        # sum from left to right using prefix sums
        if left == 0:
            return self.prefix_sums[right]
        return self.prefix_sums[right] - self.prefix_sums[left - 1]

# Driver code
arr = [2, 4, 6, 8, 10]
prefix_sum_obj = PrefixSumArray(arr)
print('Prefix sums:', ' -> '.join(map(str, prefix_sum_obj.prefix_sums)) + ' -> null')
# Example: sum from index 1 to 3 (4 + 6 + 8)
sum_1_3 = prefix_sum_obj.range_sum(1, 3)
print('Sum from index 1 to 3:', sum_1_3)

self.prefix_sums.append(self.arr[0]) # start with first element

initialize prefix sums with first element of array

self.prefix_sums.append(self.prefix_sums[i-1] + self.arr[i])

add current element to previous prefix sum to build cumulative sums

if left == 0: return self.prefix_sums[right]

if sum starts from index 0, return prefix sum at right index

return self.prefix_sums[right] - self.prefix_sums[left - 1]

subtract prefix sums to get sum of subarray from left to right

Output

Prefix sums: 2 -> 6 -> 12 -> 20 -> 30 -> null

Sum from index 1 to 3: 18

Complexity Analysis

Time: O(n) because we compute prefix sums by traversing the array once

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

vs Alternative: Without prefix sums, each subarray sum query takes O(k) time for k elements; prefix sums reduce query time to O(1) after O(n) preprocessing

Edge Cases

empty array

prefix sums remain empty, no errors occur

DSA Python

if not self.arr:
    return

single element array

prefix sums contain just that one element

DSA Python

self.prefix_sums.append(self.arr[0])  # start with first element

range sum where left equals right

returns the single element at that index correctly

DSA Python

if left == 0:
    return self.prefix_sums[right]

When to Use This Pattern

When you need to find sums of many subarrays quickly, use prefix sums to answer queries in constant time after one pass preprocessing.

Common Mistakes

Mistake: Forgetting to handle empty input array before building prefix sums
Fix: Add a check to return early if the input array is empty

Mistake: Incorrectly calculating subarray sum by not subtracting prefix sums properly
Fix: Use prefix_sums[right] - prefix_sums[left - 1] for left > 0, else prefix_sums[right]

Summary

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

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

The key insight is that sums of subarrays can be found by subtracting two prefix sums.

Practice

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

easy

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

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

C. An array where each element is the difference between consecutive elements in arr.

D. An array where each element is the sum of all elements from the start 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 from the start up to that index in arr. correctly describes this sum accumulation; others 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 D

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 stores original array values

2. Which of the following Python code snippets correctly initializes a prefix sum array prefix for an input list arr?

easy

A. prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(arr[i] - prefix[i-1])

B. prefix = []
for i in range(len(arr)):
prefix.append(arr[i] + arr[i-1])

C. prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[i-1] + arr[i])

D. prefix = [0] * len(arr)
for i in range(len(arr)):
prefix[i] = arr[i] * prefix[i-1]

Solution

1. Step 1: Analyze code for prefix sum logic

   prefix = [arr[0]] for i in range(1, len(arr)): prefix.append(prefix[i-1] + arr[i]) starts prefix with first element and adds current element to previous prefix sum correctly.

2. Step 2: Check other options for errors

   prefix = [] for i in range(len(arr)): prefix.append(arr[i] + arr[i-1]) adds current and previous array elements incorrectly; C multiplies instead of sums; A subtracts instead of sums.

3. Final Answer:

   prefix = [arr[0]]\nfor i in range(1, len(arr)):\n prefix.append(prefix[i-1] + arr[i]) -> Option C

4. Quick Check:

   Prefix sum uses cumulative addition [OK]

Hint: Start prefix with first element, then add previous prefix sum [OK]

Common Mistakes:

• Using multiplication instead of addition
• Adding wrong elements or indices
• Initializing prefix array incorrectly

3. What is the output of the following code?

arr = [3, 1, 4, 1, 5]
prefix = [arr[0]]
for i in range(1, len(arr)):
    prefix.append(prefix[i-1] + arr[i])
print(prefix)

medium

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

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

C. [3, 3, 7, 8, 13]

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

Solution

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

   Start with prefix = [3]. Then add 1: 3+1=4, add 4: 4+4=8, add 1: 8+1=9, add 5: 9+5=14.

2. Step 2: Form the final prefix array

   prefix = [3, 4, 8, 9, 14]

3. Final Answer:

   [3, 4, 8, 9, 14] -> Option A

4. Quick Check:

   Sum accumulates correctly [OK]

Hint: Add current element to last prefix sum [OK]

Common Mistakes:

• Confusing prefix array with original array
• Off-by-one errors in indexing
• Incorrect initial prefix value

4. Find the error in this prefix sum code and choose the corrected version:

arr = [2, 4, 6]
prefix = [0]
for i in range(len(arr)):
    prefix.append(prefix[i] + arr[i])
print(prefix)

medium

A. Change prefix = [0] to prefix = [arr[0]] and loop from 1 to len(arr)-1.

B. Change prefix.append(prefix[i] + arr[i]) to prefix.append(prefix[i-1] + arr[i]).

C. Remove the initial zero from prefix and start loop from 0 as is.

D. No error; code works correctly and prints prefix sums.

Solution

1. Step 1: Identify initialization and loop issues

   Initializing prefix with [0] and looping from 0 adds an extra leading zero. Tracing: i=0 append(0+2)=2 -> [0,2]; i=1 append(2+4)=6 -> [0,2,6]; i=2 append(6+6)=12 -> [0,2,6,12]. This produces prefix sums of length n+1 with prefix[0]=0, whereas standard is length n starting from arr[0].

2. Step 2: Correct initialization and loop range

   Start prefix with first element arr[0], then loop from index 1 to end to add sums correctly.

3. Final Answer:

   Change prefix = [0] to prefix = [arr[0]] and loop from 1 to len(arr)-1. -> Option A

4. Quick Check:

   Proper start and loop fix prefix sums [OK]

Hint: Initialize prefix with first element, loop from second element [OK]

Common Mistakes:

• Starting prefix with zero instead of first element
• Looping from zero causing off-by-one errors
• Using wrong prefix index inside loop

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

hard

A. Calculate sum as prefix[r] * prefix[l].

B. Calculate sum as prefix[r] - prefix[l-1] if l > 0, else prefix[r].

C. Calculate sum as prefix[r] + prefix[l] always.

D. Calculate sum by looping from l to r and adding elements.

Solution

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

   Prefix sum at index r stores sum from start to r. To get sum from l to r, subtract sum from start to l-1.

2. Step 2: Handle edge case when l is zero

   If l is zero, sum is prefix[r] directly since no subtraction needed.

3. Final Answer:

   Calculate sum as prefix[r] - prefix[l-1] if l > 0, else prefix[r]. -> Option B

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 sums instead of subtracting
• Ignoring edge case when l = 0
• Using multiplication or looping unnecessarily