Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Constant Time Array Sum using Prefix Sums
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment