Prefix Sums

JavaScript

// Counting prefix sums — O(n)

var A = [1,2,3,4,5,6,7,8,9];

function prefixSums (A) {
    var n = A.length;
    P = [0]; 
    for (var k = 1; k < n + 1; k += 1){
        P[k] = P[k - 1] + A[k - 1];
    }
    return P;
}
//console.log(A);
console.log(prefixSums(A)); // [0, 1, 3, 6, 10, 15, 21, 28, 36, 45] 

var countTotal = function (P, x, y) {
    return P[y + 1] - P[x];
}

console.log(countTotal(prefixSums(A), 5, 8)) // 30