Префиксные и суффиксные накопления

Префикс хранит результат для элементов слева от границы, а суффикс — для элементов справа. Вместе они позволяют исключить текущую позицию без повторного обхода и без операции деления.

Как получить произведение всех остальных элементов

Для массива values нужно построить массив answer той же длины, где answer[i] равен произведению всех values[j] при j != i. Например, [1, 2, 3, 4] превращается в [24, 12, 8, 6]. Деление использовать нельзя, а нули во входе допустимы.

Сколько раз прямое решение перемножает одни значения

Можно для каждого индекса i пройти весь массив и перемножить элементы с индексами j != i. Один ответ требует O(n) умножений, а все n ответов — O(n²). Решение корректно и правильно обрабатывает нули, но почти одинаковые произведения вычисляются заново.

Где повторяется произведение слева и справа

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

Разделяем ответ на левую и правую части

Обозначим:

• left[i] — произведение элементов с индексами строго меньше i;
• right[i] — произведение элементов с индексами строго больше i.

Тогда answer[i] = left[i] * right[i]. Текущий элемент не входит ни в одну часть. Сначала можно записать все левые произведения прямо в answer, затем пройти справа налево и домножить каждую позицию на текущее суффиксное произведение.

Эта идея шире произведений: когда итог для позиции раскладывается на независимый вклад слева и вклад справа, полезно искать парные префикс и суффикс. Для сумм внутренний диапазон часто получается разностью префиксов; если требуется искать прошлое накопленное значение, к префиксу добавляют словарь. Здесь деление не является безопасной обратной операцией из-за нулей, поэтому нужны обе стороны явно.

Что хранит answer после каждого прохода

После первой итерации слева направо answer[i] равен произведению values[0..i). Переменная prefix перед обработкой i хранит то же произведение; сначала она записывается, затем домножается на values[i].

Во втором проходе перед обработкой i переменная suffix равна произведению values(i..n), то есть элементов строго справа от i. Поэтому answer[i] *= suffix завершает ответ, а только затем suffix *= values[i] готовит состояние для следующей позиции слева.

Два прохода без массивов деления

1. Создать answer длины n, заполненный единицами.
2. Установить prefix = 1.
3. Слева направо записывать answer[i] = prefix, затем обновлять prefix *= values[i].
4. Установить suffix = 1.
5. Справа налево домножать answer[i] на suffix, затем обновлять suffix *= values[i].
6. Вернуть answer.

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

Произведение кроме текущего в C++ и Python

C++17

#include <cassert>
#include <vector>

using namespace std;

vector<long long> productExceptSelf(const vector<int>& values) {
    vector<long long> answer(values.size(), 1);

    long long prefix = 1;
    for (size_t index = 0; index < values.size(); ++index) {
        answer[index] = prefix;
        prefix *= static_cast<long long>(values[index]);
    }

    long long suffix = 1;
    for (size_t index = values.size(); index > 0; --index) {
        const size_t current = index - 1;
        answer[current] *= suffix;
        suffix *= static_cast<long long>(values[current]);
    }

    return answer;
}

int main() {
    assert((productExceptSelf({1, 2, 3, 4}) == vector<long long>{24, 12, 8, 6}));
    assert((productExceptSelf({-1, 1, 0, -3, 3}) == vector<long long>{0, 0, 9, 0, 0}));
    assert((productExceptSelf({0, 0, 2}) == vector<long long>{0, 0, 0}));
    assert((productExceptSelf({5}) == vector<long long>{1}));
}

Python 3

def product_except_self(values: list[int]) -> list[int]:
    answer = [1] * len(values)

    prefix = 1
    for index, value in enumerate(values):
        answer[index] = prefix
        prefix *= value

    suffix = 1
    for index in range(len(values) - 1, -1, -1):
        answer[index] *= suffix
        suffix *= values[index]

    return answer


assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
assert product_except_self([0, 0, 2]) == [0, 0, 0]
assert product_except_self([5]) == [1]

Почему два прохода остаются линейными

Оба прохода посещают каждый элемент один раз, поэтому время равно O(n). Массив ответа занимает O(n) и обязателен по контракту. Если не считать возвращаемый результат, дополнительная память равна O(1): используются только prefix, suffix и индексы.

В C++ накопления хранятся в long long; предполагается, что все промежуточные произведения помещаются в этот тип. Python использует целые произвольной точности, но стоимость операций растёт вместе с количеством цифр.

Нули, отрицательные числа и пустые стороны

• Один ноль: только позиция нуля получает произведение остальных элементов, другие ответы равны нулю.
• Два и более нуля: каждый ответ равен нулю.
• Отрицательные значения меняют знак по обычным правилам умножения.
• Один элемент: произведение пустого набора множителей принято равным 1.
• Пустой массив по контракту функции возвращает пустой массив.
• Большие множители могут переполнить фиксированный числовой тип C++.

Проверяем обе стороны и разные количества нулей

Базовый тест [1, 2, 3, 4] → [24, 12, 8, 6] проверяет обе стороны каждой внутренней позиции. [-1, 1, 0, -3, 3] → [0, 0, 9, 0, 0] проверяет один ноль и знак. [0, 0, 2] проверяет два нуля, а [5] → [1] — пустые левую и правую части.

Когда ответ раскладывается на вклад до и после позиции

Ищи префиксно-суффиксную конструкцию, если для каждого индекса нужен результат по всем элементам, кроме него, или независимые сведения о левой и правой части. Важный сигнал: соседние ответы повторно используют почти одинаковые диапазоны.

Когда нужны другие накопления или динамическая структура

Если разрешено деление и гарантировано отсутствие нулей, общее произведение даёт более короткое решение, хотя оно хуже переносится на изменённый контракт. Для частых обновлений элементов два статических прохода устаревают; тогда нужна структура для запросов и изменений диапазона. Для одного запрошенного индекса достаточно двух отдельных проходов без массива ответа.

Почему общее произведение и деление не выдерживают ноль

Вопрос. Почему нельзя всегда вычислить общий продукт и разделить его на values[i]?

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

Почему суффикс обновляется после записи ответа

Вопрос. Что сломается, если сначала выполнить suffix *= values[i], а затем answer[i] *= suffix?

Ответ. В суффикс попадёт текущий элемент, и answer[i] станет произведением всего массива, а не всех элементов кроме i. Перед домножением suffix обязан описывать только индексы строго правее.

Прослеживаем левое и правое накопления

Для [2, 3, 4] выпиши состояние после первого прохода. Подсказка: перед индексами 0, 1, 2 значения prefix равны 1, 2, 6, поэтому answer сначала становится [1, 2, 6].

Теперь иди справа: перед индексами 2, 1, 0 значения suffix равны 1, 4, 12. Домножение даёт [12, 8, 6]. Проверь отдельно, что ни один ответ не использует элемент на своей позиции.

Самостоятельная задача о двух сторонах позиции

Задача 1

Для бинарной строки постройте массив, где в позиции i записана сумма количества нулей строго слева от i и количества единиц строго справа от i. Текущий символ не учитывается. Реализуйте одинаковый контракт на C++17 и Python и приведите тесты для пустой строки и строк из одинаковых символов.

Левое и правое накопления исключают текущий элемент

Если ответ для позиции распадается на независимые части до и после неё, сохрани левую часть в результате, пройди справа с одним суффиксным состоянием и объедини их без повторного перебора.