Построение массива префиксных сумм
Заранее вычислите накопительные итоги один раз
«Построение массива префиксных сумм» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Задача о повторяющихся суммах
Представьте, что Вам нужно ответить на сотни вопросов о суммах на отрезках одного массива. Суммировать каждый отрезок с нуля медленно. Префиксная сумма решает эту проблему. 🚀
Что такое префиксная сумма
Массив префиксных сумм хранит в каждом индексе сумму всех элементов до этой позиции включительно. Один предварительный проход превращает медленные вычисления сумм в мгновенные ответы.
Небольшой пример
Для [3, 1, 4] накопленные суммы равны 3, затем 4, затем 8. Этот растущий список накопленных сумм и есть префиксная сумма.
Основная рекуррентная формула
Каждый элемент равен предыдущей сумме плюс текущий элемент. Эта однострочная рекуррентная формула лежит в основе всей техники.
prefix[i] = prefix[i - 1] + a[i]Реализация в коде
Один раз пройдите по массиву, поддерживая текущую сумму. На каждом шаге добавляйте новую сумму, поэтому построение массива выполняется за один линейный проход.
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)Почему начальный ноль помогает
Если начать prefix с начального нуля, prefix[i] будет хранить сумму первых i элементов. Это упрощает вычисления сумм на отрезках в дальнейшем.
Соглашение об индексах
При начальном нуле prefix[k] равно a[0] + ... + a[k-1]. Соблюдение этого соглашения помогает избежать неприятных ошибок на единицу.
Стоимость построения
При построении префиксного массива каждый элемент просматривается ровно один раз, поэтому требуется O(n) времени. Вы платите эту стоимость один раз, а затем используете результат снова и снова.
Предвычислите один раз, запрашивайте часто
Главное преимущество — это компромисс: один линейный проход заранее превращает каждый последующий запрос суммы в быстрое обращение к готовому значению вместо нового цикла.
Сокращение в стиле Python
Стандартная библиотека может построить накопленные суммы за Вас. itertools.accumulate создаёт последовательность текущих сумм одним аккуратным вызовом.
from itertools import accumulate
prefix = [0] + list(accumulate(a))Следите за памятью
Префиксный массив имеет ту же длину, что и входные данные, плюс один элемент. При огромных объёмах данных помните, что он вдвое увеличивает занимаемый объём памяти.
Быстрая проверка
Вы строите префиксный массив. Что обычно хранится в индексе 0?
Повторение
Вы научились строить массив префиксных сумм за один проход O(n), добавляя начальный ноль для удобной работы с индексами. Предвычислите один раз, а затем используйте результат повторно. ✅
Часто задаваемые вопросы
Урок «Построение массива префиксных сумм» бесплатный?
Да — полный текст урока «Построение массива префиксных сумм» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Построение массива префиксных сумм»?
Заранее вычислите накопительные итоги один раз Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Построение массива префиксных сумм»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Построение массива префиксных сумм
- Сумма любого диапазона вычитанием
- Подсчёт подмассивов с заданной суммой
- Массивы разностей для обновлений диапазонов