Prefix sums
From Codility.com:
There is a simple yet powerful technique that allows for the fast calculation of sums of elements in given slice (contiguous segments of array). Its main idea uses prefix sums which are defined as the consecutive totals of the first 0, 1, 2, . . . , n elements of an array.
We can easily calculate the prefix sums in O(n) time complexity. Notice that the total p(k) equals p(k−1) + a(k−1), so each consecutive value can be calculated in a constant time.
:I'm kinda dumb, so I don't still get what they are trying to explain. Let me work it out step by step.
let's say we have an array A, and:
a(0) = 0
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 4
a(5) = 5
...
and so:
let's say we have an array A, and:
a(0) = 0
a(1) = 1
a(2) = 2
a(3) = 3
a(4) = 4
a(5) = 5
...
and so:
Now I get it. The example is correct; 0 + 1 + 2 + 3 + 4 + 5 = 15. But be warned that A(0) starts one column later than P(0). This is the crucial difference. This approach is highly useful in keeping the time complexity of a function at a low rate especially when you are asked to get the sum of the first k consecutive integers in an array.