Constant Time Array Sum using Prefix Sums

constantarraysum.js

  function prefixSum(A) {
    var i = 0,
      l = A.length,
      sum = A[0],
      P = new Array(l);
    P[0] = sum;
    while (++i < l) {
      sum += A[i];
      P[i] = sum;
    }
    return P;
  }
  
  function sumPrefixSumArray(P, start, end){
    return P[end] - (P[start - 1] || 0); // prevent Out of Bounds
  }
  
  var arr = [2,5,7,4,2,4,3,3,2,1,8,6,9,7,5,4,2,5,6,7,9,0,8,5,3,2,4,5,6,7,8,5,6],
      arrSum = [],
      P = prefixSum(arr);                        // loops 33 times (arr.length)
      
  for(var i = 0, l = arr.length - 5; i < l; i++) // loops 28 times
    arrSum.push(sumPrefixSumArray(P, i, i + 4)); // 1 operation
                                                 // Total: 33 + 28 x 1 = 61 operations
  console.log("arrSum: "+arrSum);                
  // arrSum: 20,22,20,16,14,13,17,20,26,31,35,31,27,23,22,24,29,27,30,29,25,18,22,19,20,24,30,31