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

Префиксные суммы: как это работает?

Заведите массив на одну ячейку длиннее входа. Нулевая ячейка это сумма ничего, поэтому там ноль.

Пройдите вход слева направо. Каждая ячейка равна прошлой сумме плюс текущее значение.

Теперь prefix[i] это сумма первых i значений. Всё начиная с индекса i не входит.

Отрезок от l до r это весь префикс до r. Вычтите из него часть до l.

Значит ответ равен prefix[r + 1] минус prefix[l]. Это одно вычитание при любой ширине.

Массив строится один раз и читается много раз. Он перестаёт быть верным при изменении значения.

Источники: Википедия: Префиксная сумма

1. prefix = [0]Вход это [3, 1, 4, 1]. Нулевая ячейка это сумма ничего.
2. prefix = [0, 3]Прибавляем первое значение. Один элемент даёт 3.
3. prefix = [0, 3, 4]Прибавляем 1 к сумме. Два элемента дают 4.
4. prefix = [0, 3, 4, 8, 9]Остальные значения достраивают массив. Построение заняло один проход.
5. сумма(1..2) = 8 - 3 = 5На этом отрезке стоят 1 и 4. Одно вычитание, без цикла.

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]
}

function buildPrefix(arr: number[]): number[] {
    const prefix: number[] = 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: number[], l: number, r: number): number {
    return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
}

def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, val in enumerate(arr):
        prefix[i + 1] = prefix[i] + val
    return prefix

def range_sum(prefix, l, r):
    return prefix[r + 1] - prefix[l]  # sum of arr[l..r]

function buildPrefix(array $arr): array {
    $prefix = array_fill(0, count($arr) + 1, 0);
    foreach ($arr as $i => $val) {
        $prefix[$i + 1] = $prefix[$i] + $val;
    }
    return $prefix;
}
function rangeSum(array $prefix, int $l, int $r): int {
    return $prefix[$r + 1] - $prefix[$l]; // sum of arr[l..r]
}

    public static int[] buildPrefix(int[] arr) {
        int[] prefix = new int[arr.length + 1];
        for (int i = 0; i < arr.length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    public static int rangeSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
    }

    public static int[] BuildPrefix(int[] arr) {
        var prefix = new int[arr.Length + 1];
        for (int i = 0; i < arr.Length; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }
        return prefix;
    }

    public static int RangeSum(int[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l]; // sum of arr[l..r]
    }

Префиксные суммы: разбор примера

Сколько подмассивов дают сумму k

Дан массив целых чисел и число k. Посчитайте непрерывные отрезки с суммой ровно k.

Значения бывают отрицательными, поэтому окно сужать нельзя.

Идите по массиву и держите накопленную сумму.

Отрезок, кончающийся здесь, даёт k, если какой-то ранний префикс равен сумме минус k. Словарь префиксов их считает.

function subarraySum(nums, k) {
    const seen = new Map([[0, 1]]); // one empty prefix, total zero
    let total = 0;
    let count = 0;

    for (const x of nums) {
        total += x;

        // an earlier prefix of total - k closes a stretch that sums to k
        count += seen.get(total - k) ?? 0;
        seen.set(total, (seen.get(total) ?? 0) + 1);
    }

    return count;
}

Префиксные суммы: когда применять?

Паттерн «Префиксные суммы» нужен, когда в условии есть слова «много запросов на сумму по диапазону», «ответить на несколько вопросов о сумме диапазона в одном массиве» или «сумма от индекса l до r». Решение на нём обычно укладывается в O(n) build / O(1) query.

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Префиксные суммы: с чем путают?

Паттерн «Префиксные суммы» чаще всего путают с этими паттернами: Скользящее окно (фиксированный размер), Массив разностей, Дерево Фенвика / дерево отрезков и Хеш-множество / словарь.

• Скользящее окно (фиксированный размер) (Sliding window (fixed size)): Окно отвечает про один движущийся отрезок. Префиксные суммы отвечают про любой названный отрезок.
• Массив разностей (Difference array): Это зеркальный случай: много записей на отрезках, одно чтение в конце. Здесь наоборот, много чтений.
• Дерево Фенвика / дерево отрезков (Fenwick tree / segment tree): Префиксный массив ломается при первом же изменении значения. Дерево Фенвика платит log n за право менять.
• Хеш-множество / словарь (Hash set / map): У словаря нет понятия отрезка вообще. Для подсчёта подмассивов рядом нужна накопленная сумма.

Префиксные суммы: частые ошибки

• Пропускают ведущий ноль

  Тогда отрезку с нулевого индекса нечего вычитать. Массиву нужно n плюс одна ячейка.

• Ошибаются на правом крае

  Сумма от l до r читает prefix[r + 1]. Чтение prefix[r] теряет последнее значение.

• Меняют значение после построения

  Одна правка ломает все ячейки после неё. При смешанных изменениях берите дерево Фенвика.

• Дают сумме переполниться

  Миллион значений около 1e9 выходят за безопасный диапазон. Возьмите BigInt или более широкий тип.

Префиксные суммы: задачи с собеседований

Паттерн «Префиксные суммы» решает такие задачи с собеседований: Сумма на отрезке без изменений, Подмассив с суммой k, Индекс равновесия, Произведение массива кроме себя, Непрерывный подмассив с суммой, Самый длинный подмассив с суммой k и Сумма на прямоугольнике.

• Сумма на отрезке без изменений: Постройте один раз, потом отвечайте одним вычитанием.
• Подмассив с суммой k: Совместите накопленную сумму со словарём ранних префиксов.
• Индекс равновесия: Левая сумма равна общей сумме минус левая сумма минус значение.
• Произведение массива кроме себя: Та же идея, только с префиксными и суффиксными произведениями.
• Непрерывный подмассив с суммой: Храните префиксы по модулю k вместо самих сумм.
• Самый длинный подмассив с суммой k: Запоминайте первый индекс, где встретился каждый префикс.
• Сумма на прямоугольнике: Два измерения, четыре чтения на запрос.

Префиксные суммы: сложность по времени и памяти

У паттерна «Префиксные суммы» целевая сложность O(n) build / O(1) query.

n до 1e6 и много запросов на отрезках дают O(n) на подготовку. Каждый запрос стоит O(1), плюс O(n) памяти.