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

O(n) build / O(1) query

Один раз посчитать накопленную сумму, `prefix[i]` = сумма первых i элементов, тогда сумма любого диапазона `[l, r]` становится одним вычитанием вместо повторного прохода.

Сигналы

много запросов на сумму по диапазонуответить на несколько вопросов о сумме диапазона в одном массивесумма от индекса l до rнакопленная или кумулятивная сумма

Шаблон

function buildPrefix(arr) {
    const prefix = new Array(arr.length + 1).fill(0);
    for (let i = 0; i < arr.length; i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
function rangeSum(prefix, l, r) {
    return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
}

Похоже, но не то

Скользящее окно переменного размера: Окно делает один проход вперёд, чтобы найти единственный лучший непрерывный отрезок. Префиксные суммы считаются один раз заранее, чтобы потом отвечать на много произвольных, не связанных между собой диапазонов, а не искать один лучший отрезок.
Массив разностей: Префиксные суммы отвечают на много запросов ЧТЕНИЯ диапазона в фиксированном массиве. Массив разностей нужен для обратного случая: сначала много ОБНОВЛЕНИЙ диапазонов, а в конце одно финальное чтение.

n до 1e5..1e6 при многих запросах -> O(n) на построение префиксного массива один раз, затем O(1) на каждый запрос суммы диапазона вместо O(n) на запрос.

Изучить этот паттерн