Сумма подотрезка. Массив префиксных сумм
Задача
Дан неизменяемый массив длины n. Вычислить сумму элементов массива на подотрезке с l по r.
Достаточно быстро эту задачу можно решить, если сделать предварительный расчет префиксных сумм, сохранив их в дополнительный массив - массив префиксных сумм.
В информатике префиксной суммой последовательности чисел x0, x1, x2, … называется последовательность чисел y0, y1, y2, …, такая что:
y0 = x0
y1 = x0 + x1
y2 = x0 + x1+ x2
...
Идея решения заключается в том, чтобы сохранить в дополнительный массив сумму всех элементов префиксов последовательности.
В элемент с индексом 1 - значение суммы элементов префикса длиной 1 (значение первого элемента массива). В элемент с индексом 2 - значение суммы элементов префикса длиной 2 (сумма первого и второго элементов массива) и т.д.
| входное число |
1 |
2 |
3 |
4 |
5 |
6 |
... |
префиксная сумма (prefix) |
1 |
3 |
6 |
10 |
15 |
21 |
... |
Используя сформированный массив (prefix), можно легко вычислять сумму на отрезке [l; r]: prefix[r] - prefix[l-1], где prefix[r] - сумма первых r элементов последовательности, prefix[l-1] - сумма первых l-1 элементов последовательности.
