The sum of the subsegment. Array of prefix sums
Task
Given an immutable array of length n. Compute the sum of the array elements on the subsegment l to r.
This problem can be solved quickly enough if you make a preliminary calculation of prefix sums, saving them in an additional array - an array of prefix sums.
In computer science prefix sum sequences of numbers x0, x1, x2, … is called a sequence of numbers y0, y1, y2, …, such that:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1+ x2< /tt>
...
The idea of the solution is to save in an additional array the sum of all elements of the prefixes of the sequence.
To the element with index 1 - the value of the sum of prefix elements of length 1 (the value of the first array element). To the element with index 2 - the value of the sum of prefix elements of length 2 (the sum of the first and second elements of the array), etc.
| input number |
1 |
2 |
3 |
4 |
5 |
6 |
... |
prefix sum (prefix) |
1 |
3 |
6 |
10 |
15 |
21 |
... |
Using the generated array (prefix), you can easily calculate the sum on the segment [l; r]: prefix[r] - prefix[l-1], where prefix[r] is the sum of the first r elements sequences, prefix[l-1] - the sum of the first l-1 elements of the sequence.
