Prefix Sum - rFronteddu/general_wiki GitHub Wiki

The prefix sum is technique used in algorithms to efficiently calculate the sum of elements in a sequence or an array. The idea is to preprocess the array so that we can quickly calculate the sum of any subarray (a contiguous section of the array) in constant time.

Definition

Given an array A of length n, the prefix sum array P is defined as:

  • P[0] = 0 (common practice, allowing for easier calculations)
  • P[i] = A[0] + A[1] + ... + A[i - 1] for i = 1 to n

In simpler terms, P[i] represents the sum of the first i elements of the array A.

Example

Consider the array A = [3, 1, 2, 4]

  1. Constructing the Prefix Sum Array:
  • P[0] = 0
  • P[1] = 3 (sum of A[0])
  • P[2] = 3 + 1 = 4 (A[0] + A[1])
  • P[3] = 3 + 1 + 2 = 6 (A[0] + A[1] + A[2])
  • P[4] = 3 + 1 + 2 + 4 = 10 (A[0] + A[1] + A[2] + A[3])

So the prefix sum array P is: P = [0, 3, 4, 6, 10] 2. Calculate Subarray Sums:

  • To find the sum of a subarray A[l] to A[r] (inclusive), you can use the prefix sum array: sum(A[l to r]) = P[r+1] - P[l]
  • For example, to find the sum of the subarray A[1] to A[3] (which is [1, 2, 4]):
    • sum(A[1 to 3]) = P[4] - P[1] = 10 - 3 = 7

Advantages

  • Efficiency: Calculating the sum of any subarray using the prefix sum array takes O(1) time after an O(n) preprocessing
  • Useful for Multiple Queries: If you need to calculate the sum of several different subarrays, using a prefix sum array is more efficient than calculating the sum from scratch each time.