Prefix sum algorithm and its usage.

Prefix sum algorithm.js

/* We will write 2 prefix sum algorithm */
// https://www.youtube.com/watch?v=pVS3yhlzrlQ

const array = [6, 3, -2, 4, -1, 0, -5];

// Simple algorithm
const prefixSum = (array) => {  
  let result = [arr[0]]; // The first digit in the array don't change
  array.reduce((accumulator, current) => {
    result.push(accumulator + current); // next will be previous sum plus current digit
    return accumulator + current; // update accumulator
  });
  return result;
}

// online function
const result = array.reduce(function(a,b,i){ return i === 0 ?  [b]: a.concat(a[i-1]+b);},0);

// result = [ 6, 9, 7, 11, 10, 10, 5 ]

/* Prefix sum algorithm application */

// 1. Calculate the sum between range [0, 4]?
//    Answer = 4th index of the result which is result[4]=10.
// 2. Calculate the sum between range [2, 6] ? Answer = -4
//    [0, 6] = [0, 1] + [2, 6]
//    5 = 9 + x
//    x = 5 - 9 = -4
// Formula for calculating sum between range: A[i, j] = A[j]  - A[i - 1];
const sumBetweenRange = (prefixSum, i, j) => {
  if(i === 0) return prefixSum[prefixSum.length - 1];
  return prefixSum[j] - prefixSum[i -1];
}