Почему тема префиксных сумм важна
Префиксные суммы встречаются почти в каждом варианте ЕГЭ. Экзаменаторы любят их за простоту идеи и широкий спектр задач. Школьник, который уверенно считает такие суммы, быстро набирает баллы. Тема хорошо тренирует алгоритмическое мышление. Кроме того, она показывает, как одна строка кода экономит секунды выполнения. Это особенно важно в заданиях, где входные данные велики. В итоге владение префиксными суммами повышает итоговый балл и уверенность на экзамене.
Базовая идея на пальцах
Допустим, у нас ряд чисел. Мы хотим быстро узнать сумму любого отрезка. Наивный способ пересчитает все элементы каждый раз. Он медленный. Префиксная сумма копит частичные результаты. Сначала вычисляем массив P, где P[i] — сумма первых i элементов исходного массива A. Тогда сумма от l до r равна P[r] − P[l − 1]. Расчёт превращается в две операции, а не в десятки. Принцип подходит не только для суммы. Аналогично работают префиксные произведения, минимумы или XOR.
Формальное определение
Пусть дан массив A длиной n, индексация с единицы. Префиксный массив P определим так:
- P[0] = 0;
- для i = 1…n: P[i] = P[i − 1] + A[i].
Сумма отрезка A[l…r] вычисляется как P[r] − P[l − 1]. Сложность предобработки O(n). Каждой дальнейшей операции запроса нужна лишь O(1). Поэтому метод спасает при большом числе запросов. Если запросов мало, то выгода меньше, но формула остаётся полезной как средство проверки.
Типовые задачи из ЕГЭ
Рассмотрим несколько жанров.
- Подсчёт количества пар с заданной суммой. Префикс помогает получить сумму префикса, а затем вычислить остаток.
- Поиск максимальной среднеарифметической подпоследовательности фиксированной длины. Необходимо быстро получать сумму каждого окна.
- Задачи на анализ объёма памяти. Даны размеры файлов, требуется определить, сколько файлов поместится. Здесь префиксные суммы позволяют мгновенно узнать суммарный объём первых k файлов.
- Работа со строками. Иногда символы кодируют числа. Требуется проверить равенство сумм двух частей слова.
Во всех примерах правильная предобработка экономит минуты. А на экзамене время золото.
Реализация на разных языках
Python:
n = int(input())
a = list(map(int, input().split()))
p = [0]
for x in a:
p.append(p[-1] + x)
l, r = map(int, input().split())
print(p[r] - p[l - 1])C++:
int n; cin >> n;
vector<long long> a(n + 1), p(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
p[i] = p[i - 1] + a[i];
}
int l, r; cin >> l >> r;
cout << p[r] - p[l - 1];Java:
int n = in.nextInt();
long[] p = new long[n + 1];
for (int i = 1; i <= n; i++) {
p[i] = p[i - 1] + in.nextLong();
}
int l = in.nextInt(), r = in.nextInt();
out.println(p[r] - p[l - 1]);Код короткий. Но ошибки случаются. Чуть ниже разберём типичные.
Частые ошибки
Смещения индексов. Ученики путают нулевую и первую позиции. Проверяем формулу на простом примере, где сумма легко считается вручную. Второй провал — забытый тип long long в C++. При больших входах происходит переполнение, и ответ неверен. Третья проблема — неочищенный массив между тестами в системах с многократным запуском кода. Всегда инициализируем p[0] нулём. Наконец, строки во входном файле иногда содержат лишние пробелы. Используем аккуратный парсинг.
Как тренироваться
Методика проста.
- Сначала решаем базовые задачи на одном запросе. Осваиваем формулу.
- Переходим к множеству запросов. Здесь префиксные суммы уже обязательны.
- Добавляем ограничения на память. Учимся хранить только важное.
- После закрепления навыка меняем домен задачи: числа, символы, вероятности.
- Сравниваем свой код с эталонным решением. Ищем лишние циклы.
- Раз в неделю пишем мини-контрольную. Засекаем время.
Если нужна системная поддержка, присмотритесь к онлайн школе подготовки к ЕГЭ. Там можно получить живую обратную связь и новые задачи.
Мини чек-лист перед экзаменом
Перед входом в аудиторию повторите короткий набор действий.
- Убедитесь, что помните формулу P[r] − P[l − 1].
- Вспомните отличие индексации с нуля и с единицы.
- Проверьте готовые шаблоны кода на своём языке.
- Отдельно подумайте о типах данных. Суммы могут быть большие.
- Помните, что одна ошибка со смещением загубит решение.
- Не тратьте время на длинный вывод. Пишите компактно, но читабельно.
- Если в задаче мало запросов, всё равно мысленно проверьте идею префикса. Иногда она спасает от опечаток.
Следуя этим пунктам, вы сэкономите нервы и заработаете баллы.