Скользящее окно отлично работает, когда отрезок один и он ползёт. А если отрезки произвольные и их много: «сколько заработали с третьего по десятое», потом «с первого по пятое», и так тысячу раз? Каждый раз складывать заново — O(N) на запрос. Приём префиксных сумм отвечает на такой запрос за O(1) после одного подготовительного прохода.

Идея: нарастающий итог

Заведём массив, в котором на месте i лежит сумма всех элементов до i. Это и есть нарастающий итог — то же самое, что накопленная выручка с начала года.

Тогда сумма на отрезке — просто разность двух накопленных итогов: «сколько накопилось к концу отрезка» минус «сколько накопилось к его началу». Всё, что до начала отрезка, вычитается и не мешает.

class Revenue {
    private final long[] prefix;

    Revenue(int[] daily) {
        prefix = new long[daily.length + 1];
        for (int i = 0; i < daily.length; i++) prefix[i + 1] = prefix[i] + daily[i];
    }

    long range(int l, int r) {
        return prefix[r + 1] - prefix[l];
    }
}

Подготовка — O(N) один раз. Каждый запрос — O(1). При тысяче запросов на миллионе дней это разница между «мгновенно» и «полминуты».

Почему массив на единицу длиннее

Обратите внимание: prefix длиннее исходного массива, а prefix[0] равен нулю. Это не случайность, а способ избавиться от особого случая.

Если бы префиксы совпадали с данными по длине (prefix[i] = сумма по i включительно), то формула была бы prefix[r] - prefix[l - 1], и при l == 0 мы обратились бы к prefix[-1]. Пришлось бы каждый раз писать проверку. Лишний нулевой элемент в начале — это «пустая сумма», и она делает формулу единообразной для всех отрезков.

Такой приём — добавить фиктивный элемент, чтобы убрать особый случай — встречается часто; в связных списках ту же роль играет фиктивная голова.

Не только суммы

Приём работает с любой операцией, у которой есть обратная. Чаще всего это сложение, но полезны и производные варианты.

Количество по признаку. Чтобы быстро отвечать «сколько отменённых заказов между днями l и r», строим префиксы не по выручке, а по единицам и нулям: единица, если заказ отменён. Сумма на отрезке превращается в количество.

Среднее. Сумма на отрезке, делённая на длину отрезка, — тоже O(1).

А вот с минимумом или максимумом приём не работает: у них нет обратной операции, из «минимума на префиксе» нельзя вычесть лишнее. Для таких запросов нужны другие структуры — например, кучи или деревья отрезков.

Обратная задача: много изменений, один запрос

Бывает наоборот: отрезки не читают, а массово прибавляют к ним число, и только в конце нужен итоговый массив. «Прибавь по единице к каждому дню акции» — и таких акций тысячи.

Тут помогает зеркальный приём — разностный массив. Вместо того чтобы трогать весь отрезок, отмечаем только два места: в начале отрезка прибавляем, сразу за концом вычитаем.

static int[] applyRanges(int days, int[][] ranges) {
    int[] diff = new int[days + 1];
    for (int[] r : ranges) {
        diff[r[0]] += 1;
        diff[r[1] + 1] -= 1;
    }
    int[] result = new int[days];
    int running = 0;
    for (int i = 0; i < days; i++) {
        running += diff[i];
        result[i] = running;
    }
    return result;
}

Каждое изменение — O(1) вместо O(длины отрезка), а в конце один проход с нарастающим итогом восстанавливает ответ. По сути это префиксные суммы, применённые наоборот.

Два измерения

Если данные лежат таблицей (например, продажи по дням и складам), тот же приём распространяется на прямоугольники. В prefix[i][j] кладут сумму всего прямоугольника от левого верхнего угла до клетки (i, j).

Сумма произвольного прямоугольника считается из четырёх чисел: берём большой прямоугольник, вычитаем полосу слева и полосу сверху — при этом угол вычли дважды, поэтому его возвращают обратно. Подготовка — O(N·M), любой запрос — O(1).

Чем платим

Приём не бесплатный, и стоит помнить о трёх вещах.

Память. Нужен дополнительный массив размера с исходный. Для двумерного случая — целая таблица.

Только неизменяемые данные. Если элемент поменялся, все префиксы после него становятся неверными и требуют пересчёта за O(N). Префиксные суммы хороши там, где данные записали один раз и много раз читают.

Переполнение. Суммы растут, и int кончается быстрее, чем кажется: миллион дней по паре тысяч — уже за пределами диапазона. В примерах выше префиксы объявлены как long именно поэтому.

Коротко

  • Префиксные суммы — предподсчитанный нарастающий итог; сумма любого отрезка становится разностью двух чисел.
  • Подготовка O(N) один раз, каждый запрос O(1) — приём окупается, когда запросов много.
  • Массив префиксов делают на единицу длиннее с нулём в начале: так формула работает и для отрезка с нулевой позиции.
  • Работает с суммой и количеством по признаку; не работает с минимумом и максимумом — у них нет обратной операции.
  • Зеркальный вариант — разностный массив: массовые прибавления к отрезкам за O(1) каждое, итог собирается одним проходом в конце.
  • Ограничения: лишняя память, данные должны быть неизменяемыми, суммы легко переполняют int.

Дальше — двоичный поиск по ответу: что делать, когда ответ нельзя вычислить напрямую, но легко проверить.