Prefix Sums

prefix-sums.md

Prefix Sums

Prefix sums is a tehnique that allows for the calculation of the sums M slices of a given array in constant time - O(1)

Given an array of length N, it's prefix sums can be calculated in linear time - O(N) like this

function prefixSums(A) {
  const sums = new Array(A.length + 1).fill(0);

  for (let i = 1; i < sums.length; i++) {
    sums[i] = sums[i - 1] + A[i - 1];
  }

  return sums;
}

Now using the prefix sums, we can calculate the total of any slice of array, A with length N in O(1)

/**
 * P ==> Prefix sums
 * X ==> start index of array slice - 0 <= X < Y
 * Y ==> end index of array slice - X < Y <= N
 */
function sliceTotal(P, X, Y) {
  return P[Y + 1] - P[X];
}

If we had M slices, the total time complexity will be O(M+N). Doing this using a regular for loop to calculate is slice-sum will produce a time complexity of O(M*N)