Пусть имеется некоторый массив. При отсутствии изменений мы можем быстро (быстрее, чем за линию) находить значение некоторых функций на подотрезке данного массива. Для этого нам необходимо использовать дополнительную память и сделать предподсчет.
Например, нам необходимо быстро находить сумму на некотором отрезке массива.
Заведем массив префиксных сумм, в котором по индексу 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.