Что именно хранит префикс
Пронумеруем элементы с единицы и возьмём массив из пяти чисел: 4, −2, 7, 1, −3. Перед первым элементом мысленно поставим накопленную сумму ноль. После первого числа сумма равна четырём, после второго двум, после третьего девяти, после четвёртого десяти, после пятого семи. Получается вспомогательная последовательность: 0, 4, 2, 9, 10, 7. Каждый её элемент отвечает на вопрос, сколько составляет сумма от начала исходного массива до соответствующей позиции включительно. Начальный ноль обозначает пустой участок перед массивом. Он нужен не для красоты: благодаря ему отрезки, начинающиеся с первой позиции, обрабатываются по тому же правилу, что и остальные.
Почему вычитается позиция перед левой границей
Найдём сумму со второй по четвёртую позицию включительно. Накопленная сумма до четвёртой позиции равна десяти, но в ней присутствует лишний первый элемент. Сумма до позиции перед левой границей равна четырём. Вычитаем четыре из десяти и получаем шесть. Прямая проверка даёт тот же ответ: минус два плюс семь плюс один. Общее правило такое: возьмите накопленную сумму до правой границы и вычтите накопленную сумму до позиции непосредственно перед левой границей. Если вычесть префикс до самой левой границы, первый нужный элемент тоже исчезнет. Это типичная ошибка, которую легко заметить на отрезке из одного элемента. Отрицательные числа не мешают приёму. Накопленная сумма может уменьшаться, поэтому воспринимать её как обязательно возрастающую последовательность нельзя. Вычитание работает за счёт удаления одинаковой начальной части, а не за счёт роста значений.
Когда подготовка окупается
Для построения префиксов нужно один раз пройти по всем элементам. После этого каждый запрос требует обращения к двум накопленным значениям и вычитания. При обычном подсчёте стоимости арифметических операций подготовка занимает время, пропорциональное длине массива, а обработка всех запросов добавляет время, пропорциональное их количеству. Дополнительно требуется память для префиксов. У метода есть важное условие: накопленные значения должны соответствовать текущему массиву. Если изменить исходный элемент, часть сохранённых префиксов устареет. Для редких изменений их можно пересчитать; при частых обновлениях стоит рассматривать другие структуры данных. Также необходимо выбрать числовой тип, способный вместить общую сумму: подходящий диапазон для отдельного элемента может оказаться недостаточным для накопленного результата.
Попробуйте на практике
На бумаге постройте префиксные суммы для массива 4, −2, 7, 1, −3 и проверьте три разных вида отрезков.
- Запишите позиции от первой до пятой. Рядом сделайте отдельную строку накопленных сумм, начиная с нуля перед первой позицией.
- Последовательно прибавьте каждый элемент и получите шесть накопленных значений. Проверьте, что отрицательные элементы уменьшают текущую сумму.
- Посчитайте отрезки со второй по четвёртую позицию, с первой по пятую и с третьей по третью. Каждый раз сначала назовите две нужные границы префиксов.
- Сложите элементы каждого отрезка напрямую и сравните ответы. Затем мысленно измените второй элемент и отметьте, какие накопленные значения пришлось бы пересчитать.
Как проверить результат. Ответы для трёх отрезков равны шести, семи и семи. После изменения второго элемента устаревают префиксы начиная со второй позиции. Если одиночный отрезок дал ноль, проверьте, не вычли ли вы префикс до самой левой границы.
Частые вопросы
Можно ли использовать этот способ для одного запроса?
Можно, но предварительное построение всех префиксов не обязательно даст преимущество перед прямым сложением нужного участка. Польза особенно заметна при повторных запросах к неизменному массиву.
Как считать отрезок, начинающийся с первого элемента?
Из префикса до правой границы вычитается начальный ноль. Отдельная формула не нужна: правило сохраняется и для этой границы.
Самостоятельный разбор темы. Содержание конкретной обучающей программы здесь не представлено.