PrefixSum Algorithm

Posted on by user

The Prefix Sum algorithm is a technique primarily used to efficiently calculate the sum of elements in a given range (i.e., sum of elements from index i to j) in an array. This technique is helpful in situations where there are multiple range sum queries on an array and you want to avoid recalculating the sum every time.

How Prefix Sum Works

  1. Preprocessing Step: Create a prefix sum array where each element at index i stores the sum of elements from the beginning of the array up to index i.
  2. Querying: To find the sum of elements from index i to j, you simply calculate prefixSum[j] - prefixSum[i-1]. For the sum from the start of the array to j, it’s just prefixSum[j].

Example in Python

Here’s a simple Python example to illustrate:

def createPrefixSum(arr):
    prefixSum = [0] * len(arr)
    prefixSum[0] = arr[0]
    for i in range(1, len(arr)):
        prefixSum[i] = prefixSum[i-1] + arr[i]
    return prefixSum

def rangeSum(prefixSum, i, j):
    if i == 0:
        return prefixSum[j]
    else:
        return prefixSum[j] - prefixSum[i-1]

# Example usage
arr = [1, 2, 3, 4, 5]
prefixSumArr = createPrefixSum(arr)
print(rangeSum(prefixSumArr, 1, 3))  # Sum of elements from index 1 to 3

Example Problems Solvable by Prefix Sum

  1. Range Sum Queries: As described above, finding the sum of elements in a given range multiple times.
  2. Finding the Equilibrium Index in an Array: An index where the sum of elements at lower indexes is equal to the sum of elements at higher indexes.
  3. Subarray with Given Sum: Find if there is a subarray with a given sum.
  4. Count Subarrays with Given XOR: This problem can be solved using a combination of prefix sum and hash map techniques.
  5. Maximum Average Subarray: Finding the subarray with the maximum average value.
  6. Cumulative Frequency Count: Useful in scenarios like processing the number of events occurring up to each time point.

These are just a few examples, and there are many more problems, especially in competitive programming and data analysis, where the prefix sum technique can be very useful.

The concept of a “prefix sum” array is a useful technique in computer science for efficiently calculating the sum of elements in a subarray of an original array. Let’s break down the explanation:

  1. What is a Prefix Sum Array?
  • A prefix sum array is an auxiliary array that stores the cumulative sum of elements from the start of the original array up to a certain point. This technique is beneficial for quickly calculating the sum of elements in a range without the need to sum up the elements each time.
  1. How is it Constructed?
  • Given an original array a, indexed from 0 to n-1, a prefix sum array s is created with n+1 elements (one more than the original array).
  • s[0] is initialized to 0. This is a key aspect as it represents the sum of zero elements.
  • For each k (from 1 to n), s[k] is the sum of the first k elements of the original array. Formally, s[k] = a[0] + a[1] + ... + a[k-1].
  1. How to Use it for Summing Subarrays?
  • To find the sum of a subarray from start to end in the original array a, you use the formula: sum(start, end) = s[end+1] - s[start].
  • This works because s[end+1] is the sum of elements from 0 to end, and s[start] is the sum of elements before the start. Subtracting these gives the sum of the subarray start to end.
  1. Example:
  • Consider an array a = [1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1].
  • The corresponding prefix sum array s would be [0, 1, 1, 1, 2, 3, 3, 4, 4, 4, 5, 6, 6, 7].
  • To calculate the sum of the subarray from start=0 to end=3 in a, we use s[3+1] - s[0], which equals 2 - 0 = 2. This is the sum of [1, 0, 0, 1].

The advantage of this method is its efficiency. After the prefix sum array is constructed, each subarray sum can be calculated in constant time, which is particularly beneficial when dealing with multiple sum queries on the same array.