Prefix Sums (Cumulative Sums) in Python

Prefix sums (also known as cumulative sums) are a powerful technique in Python for efficiently calculating the sum of elements within a given range of a list or array. This method pre-computes the sum of all elements up to each index, allowing for constant-time (O(1)) range sum queries.

This article provides a detailed guide on how to use prefix sums in Python, complete with practical examples and code implementations to enhance your data analysis skills. We’ll explore different methods to calculate and utilize prefix sums using Python and its libraries like NumPy.

Consider the following list:

 Input: [1, 2, 3, 4, 5]
 

The prefix sum would be:

 Output: [1, 3, 6, 10, 15]
 

Method 1: Basic Prefix Sum Calculation Using a Loop

This method demonstrates how to calculate prefix sums using a simple Python loop. It’s a straightforward approach that’s easy to understand and implement.

 def prefix_sum_loop(nums):
     prefix = [0] * len(nums)
     prefix[0] = nums[0]
     for i in range(1, len(nums)):
         prefix[i] = prefix[i-1] + nums[i]
     return prefix

 nums = [1, 2, 3, 4, 5]
 prefix_sums = prefix_sum_loop(nums)
 print(prefix_sums)
 

 [1, 3, 6, 10, 15]
 

Explanation: The code initializes a new list called prefix with the same length as the input list nums. The first element of prefix is set to the first element of nums. Then, the code iterates through the remaining elements of nums, calculating each prefix sum by adding the current element of nums to the previous prefix sum. The result is a list containing the cumulative sums at each index.

Method 2: Prefix Sum Using the accumulate Function from itertools

The itertools module provides the accumulate function, which offers a more concise and efficient way to calculate prefix sums. This is often preferred for its readability and performance.

 from itertools import accumulate

 def prefix_sum_accumulate(nums):
     return list(accumulate(nums))

 nums = [1, 2, 3, 4, 5]
 prefix_sums = prefix_sum_accumulate(nums)
 print(prefix_sums)
 

 [1, 3, 6, 10, 15]
 

Explanation: This code uses the accumulate function from the itertools module to calculate the prefix sums of the input list nums. The accumulate function returns an iterator, which is then converted to a list. It’s a more compact and often faster way to achieve the same result as the manual loop.

Method 3: Prefix Sum Using NumPy

NumPy offers a highly optimized way to calculate prefix sums using the cumsum function. This is particularly useful when dealing with large arrays due to NumPy’s efficient array operations.

 import numpy as np

 def prefix_sum_numpy(nums):
     arr = np.array(nums)
     return arr.cumsum().tolist()

 nums = [1, 2, 3, 4, 5]
 prefix_sums = prefix_sum_numpy(nums)
 print(prefix_sums)
 

 [1, 3, 6, 10, 15]
 

Explanation: First, the input list nums is converted into a NumPy array. Then, the cumsum method is called on the NumPy array, calculating the cumulative sums efficiently. Finally, the result is converted back into a Python list for compatibility. NumPy’s implementation is usually the fastest, especially for large datasets.

Method 4: Calculating Range Sums Using Prefix Sums

Once you have the prefix sums, you can efficiently calculate the sum of any range of elements in the original list. This method shows how to do that.

 def range_sum(prefix_sums, start, end):
     if start == 0:
         return prefix_sums[end]
     else:
         return prefix_sums[end] - prefix_sums[start - 1]

 nums = [1, 2, 3, 4, 5]
 prefix_sums = prefix_sum_loop(nums) # Using our loop-based function for demonstration
 print(f"Prefix Sums: {prefix_sums}")
 start_index = 1
 end_index = 3
 range_sum_value = range_sum(prefix_sums, start_index, end_index)
 print(f"Sum from index {start_index} to {end_index}: {range_sum_value}")
 

 Prefix Sums: [1, 3, 6, 10, 15]
 Sum from index 1 to 3: 9
 

Explanation: This code defines a function range_sum that takes the prefix sums list, a start index, and an end index as input. It calculates the sum of the range by subtracting the prefix sum at start - 1 from the prefix sum at end. If the start index is 0, it simply returns the prefix sum at the end index. This allows for O(1) range sum queries after the prefix sum is computed.

Method 5: Prefix Sum for 2D Arrays (Matrices)

The concept of prefix sums can also be extended to 2D arrays, enabling efficient computation of submatrix sums.

 import numpy as np

 def prefix_sum_2d(matrix):
     rows, cols = len(matrix), len(matrix[0])
     prefix_sums = np.zeros((rows + 1, cols + 1), dtype=int)

     for i in range(1, rows + 1):
         for j in range(1, cols + 1):
             prefix_sums[i, j] = matrix[i-1][j-1] + prefix_sums[i-1, j] + prefix_sums[i, j-1] - prefix_sums[i-1, j-1]

     return prefix_sums

 def submatrix_sum(prefix_sums, row1, col1, row2, col2):
     return prefix_sums[row2+1, col2+1] - prefix_sums[row1, col2+1] - prefix_sums[row2+1, col1] + prefix_sums[row1, col1]

 matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
 prefix_sums = prefix_sum_2d(matrix)
 print("Prefix Sum Matrix:")
 print(prefix_sums)

 row1, col1, row2, col2 = 0, 0, 1, 1
 submatrix_sum_value = submatrix_sum(prefix_sums, row1, col1, row2, col2)
 print(f"Sum of submatrix from ({row1}, {col1}) to ({row2}, {col2}): {submatrix_sum_value}")
 

 Prefix Sum Matrix:
 [[ 0  0  0  0]
  [ 0  1  3  6]
  [ 0  5 12 21]
  [ 0 12 27 45]]
 Sum of submatrix from (0, 0) to (1, 1): 12
 

Explanation: The prefix_sum_2d function calculates the prefix sum matrix for a given 2D matrix. The submatrix_sum function then uses this prefix sum matrix to efficiently compute the sum of any submatrix defined by the top-left corner (row1, col1) and bottom-right corner (row2, col2). This technique dramatically speeds up calculations involving submatrix sums, which are common in image processing and other applications.