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

Предварительный подсчёт для быстрых запросов

Если сумму на одном отрезке массива нужно посчитать один раз, достаточно обычного цикла. Но если таких запросов много, повторный обход одних и тех же элементов становится лишней работой. Префиксные суммы переносят часть вычислений в предварительный этап.

Создадим массив prefix, где каждый элемент хранит сумму всех значений до текущей позиции. Удобно сделать его на одну ячейку длиннее исходного массива:

int[] prefix = new int[numbers.length + 1];

for (int i = 0; i < numbers.length; i++) {
    prefix[i + 1] = prefix[i] + numbers[i];
}

Теперь prefix[k] содержит сумму первых k элементов. Например, prefix[0] равно нулю, а prefix[3] — сумме элементов с индексами 0, 1 и 2.

Сумма отрезка через разность

Чтобы получить сумму элементов от индекса left включительно до right исключительно, достаточно вычесть два префикса:

int rangeSum = prefix[right] - prefix[left];

В prefix[right] находятся все элементы до правой границы, а prefix[left] убирает часть, расположенную до левой границы. После подготовки массива каждый такой запрос выполняется за O(1).

Цена подготовки

Построение префиксов требует O(n) времени и O(n) дополнительной памяти. Это имеет смысл, когда после подготовки нужно отвечать на много запросов по одному и тому же массиву. Для единственного запроса обычный проход может быть проще.