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

В теме Структуры данных · Учебная карта
Главная мысль
Префиксная сумма P(k) хранит сумму первых k элементов, причём P(0)=0. Сумма элементов с индексами от l включительно до r исключительно равна P(r)−P(l). После подготовки массива каждый такой запрос требует двух чтений и одного вычитания.
Число элементов вместо последнего индекса
В журнале записаны результаты [4, −1, 6, 2, 5]. Индексы начинаются с нуля. Создадим массив P=[0, 4, 3, 9, 11, 16]. У него на одну клетку больше, потому что отдельно хранится сумма пустого начала. P(3)=9 складывает ровно три значения: 4, −1 и 6.
Нулевая клетка убирает специальный случай для запроса от самого начала. Важно сначала подписать, что означает аргумент: «первые k элементов» и «до индекса k включительно» — разные договорённости. Обе возможны, но смешение их в одной формуле приводит к пропуску или лишнему элементу.
Пример
Сумма полуинтервала [1,4) равна P(4)−P(1)=11−4=7.
Проверка прямым сложением: −1+6+2=7. Правый индекс 4 указывает на первый элемент, который уже не входит в запрос.
Почему вычитание удаляет ненужное начало
В P(r) входят все значения перед r, в том числе участок перед l. В P(l) находится ровно этот лишний участок. При вычитании он сокращается, а отрезок от l до r остаётся. Аргумент работает и для отрицательных чисел: положительность элементов здесь не нужна.
Пустой полуинтервал [l,l) даёт P(l)−P(l)=0. Полный массив описывается [0,n), его сумма равна P(n). Если пользователь вводит номера дней с единицы и обе границы включены, перед запросом их переводят: дни a…b соответствуют индексному полуинтервалу [a−1,b).
Когда готовая таблица перестаёт отвечать верно
Заменим в журнале значение с индексом 2: вместо 6 стало 10. Все префиксы, которые уже включают эту позицию, должны увеличиться на 4. Старый массив P больше не подходит, даже если формула запроса написана без ошибок. Начало массива до изменённого места остаётся прежним.
Для редких изменений можно перестраивать префиксы. При частых обновлениях используют другую структуру, например дерево Фенвика. Сами префиксные суммы особенно удобны для множества запросов к неизменному набору. Подготовка занимает линейное время и дополнительную память; при одном запросе прямое сложение иногда проще. Перед чтением двух клеток проверяют допустимость обеих границ и их порядок. Отрицательный индекс некоторых языков означает доступ с конца массива, поэтому ошибочная левая граница может дать правдоподобный ответ вместо явного сбоя.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли так же вычитать префиксные минимумы?
Нет: минимум не имеет обратной операции, которая удаляла бы влияние начала. Например, одинаковый минимум двух префиксов ничего не говорит о минимуме между их границами.
Что проверять при больших числах?
Тип итоговой суммы должен вмещать накопленное значение. Даже если каждый элемент помещается в узкий целый тип, сумма многих элементов может выйти за его диапазон.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как две отметки задают прибавку на целом диапазоне
Восстанавливаем изменения по разностям, прибавляем значение на включённом диапазоне и объясняем отменяющую отметку сразу после его конца.
Открыть темуКак найти ошибку на границе цикла
Как находить ошибку на один шаг в цикле Python: включённое начало, исключённая правая граница range и допустимые индексы списка.
Открыть тему