Префиксные суммы
В информатике префиксной суммой последовательности чисел x0, x1, x2, … xn-1 называется последовательность чисел y0, y1, y2, …, yn такая что:
y0 = 0
y1 = x0
y2 = x0 + x1
y3 = x0 + x1+ x2
...
Обратите внимание на то, что yi — это сумма первых i элементов массива x. Другими словами yi — это сумма элементов массива x на полуинтервале [0, i),
Рекуррентная формула
Формулу для yi можно записать рекурсивно:
y0 = yi
yi+1 = yi + ai, для всех i ≥ 0
Задача
Дан неизменяемый массив длины n. Вычислить сумму элементов массива на подотрезке с l по r.
Идея решения заключается в том, чтобы сохранить в дополнительный массив сумму всех элементов префиксов последовательности (
массив префиксных сумм). В элемент с индексом 1 - значение суммы элементов префикса длиной 1 (значение первого элемента массива). В элемент с индексом 2 - значение суммы элементов префикса длиной 2 (сумма первого и второго элементов массива) и т.д.
| входное число |
|
1 |
2 |
3 |
4 |
5 |
6 |
... |
префиксная сумма (prefix) |
0 |
1 |
3 |
6 |
10 |
15 |
21 |
... |
Используя сформированный массив (prefix), можно легко вычислять сумму на отрезке
[l; r]: prefix[r+1] - prefix[l], где
prefix[r+1] - сумма первых
r элементов последовательности,
prefix[l] - сумма первых
l элементов.последовательности.
Графически эту идею можно изобразить следующим образом: элементы массива находятся в ячейках, а префиксные суммы находятся между ними — на перегородках. И содержат в себе суммы всего того, что находится перед этой перегородкой: