Prefix Sum

Prefix sum is a technique used to calculate the sum of elements in a given range in constant time. It is also known as cumulative sum.

The prefix sum of an array is an array of the same length where the element at index i is the sum of all elements in the array from index 0 to i.

This is the formula to calculate the prefix sum of an array:

prefixSum[i] = arr[0] + arr[1] + ... + arr[i]

or equivalently:

prefixSum[i] = prefixSum[i-1] + arr[i]

Problem Statement

Given an array arr of size n, the task is to calculate the prefix sum of the array.

Example:

Given an array arr = [1, 2, 3, 4, 5], the prefix sum of the array is [1, 3, 6, 10, 15].

Approach

The prefix sum of an array can be calculated using the following steps:

  1. Initialize an array prefixSum of size n with all elements as 0.
  2. Iterate over the array arr from index 1 to n and calculate the prefix sum of the array.
  3. Update the prefixSum array with the sum of the current element and the previous element.

Pseudocode

function prefixSum(arr):
    n = length of arr
    prefixSum = array of size n with all elements as 0
    prefixSum[0] = arr[0]
    for i = 1 to n-1:
        prefixSum[i] = prefixSum[i-1] + arr[i]
    return prefixSum

Complexity Analysis

The time complexity of the prefix sum algorithm is O(n) where n is the size of the input array. The space complexity of the algorithm is O(n) as we are using an additional array of size n to store the prefix sum.

Implementation

Here is the implementation of the prefix sum algorithm in Python:

def prefix_sum(arr : list) -> list:
    n = len(arr)
    prefix_sum = [0] * n # Initialize an array of size n with all elements as 0
    prefix_sum[0] = arr[0]

    for i in range(1, n):
        prefix_sum[i] = prefix_sum[i - 1] + arr[i]

    return prefix_sum

# Test the prefix sum algorithm
arr = [1, 2, 3, 4, 5]
print(prefix_sum(arr))  # Output: [1, 3, 6, 10, 15]

Applications

The prefix sum technique is widely used in various algorithms and problems, such as:

Summary

Prefix sum is a useful technique for calculating the sum of elements in a given range in constant time. It is commonly used in algorithms and problems that require calculating cumulative sums efficiently. By precomputing the prefix sum of an array, we can answer range sum queries in O(1) time complexity.

References

Related Posts