Префиксные суммы

Пусть имеется некоторый массив. При отсутствии изменений мы можем быстро (быстрее, чем за линию) находить значение некоторых функций на подотрезке данного массива. Для этого нам необходимо использовать дополнительную память и сделать предподсчет.
Например, нам необходимо быстро находить сумму на некотором отрезке массива.
Заведем массив префиксных сумм, в котором по индексу i будет сумма всех элементов массива с индексами меньшими либо равными i.
a[] – данный массив, p[] – массив префиксных сумм


Подсчет массива p:
Очевидно p[0] = a[0]. Заметим, что мы легко можем пересчитать значение p[i] через p[i – 1], т.к. сумма на префиксе i это сумма на префиксе i – 1 + a[i].
Таким образом, код подсчета префиксных сумм выглядит следующим образом:

int a[n], p[n];
p[0] = a[0];
for (int i = 1; i < n; i++)
         p[i] = p[i - 1] + a[i];

Далее заметим, что сумма на отрезке – разница двух сумм на префиксе.


Зеленый = красный – синий
Таким образом, если необходимо найти сумму на отрезке [l,r], то ответ равен p[r] – p[l-1].
Однако, если l – 1 элемента может не существовать. Для того, чтобы обойтись без if’ов можно ввести 1-индексацию, а в a[0] и p[0] будут нейтральные значения (0 для суммы).
 
Заметим, что данный прием является частным случаем формулы включений-исключений, поэтому данным образом возможно хранить не только суммы, но и другие функции, например, умножения и xor.