Алгоритмы
Prefix Sum: Предвычисление сумм
Цели урока
- Понять идею предвычисления для ускорения запросов
- Строить и использовать prefix sum массив
- Применять difference array для обновлений на отрезках
- Расширить технику на двумерные массивы
Предварительные знания
- Базовые структуры данных: массивы
- Понимание анализа сложности O(n)
Prefix Sum - одна из самых частых оптимизаций на собеседованиях.
- Если видите 'сумма на отрезке', сразу думайте о prefix sum
- Основа для более сложных структур: Fenwick Tree и Segment Tree
От APL Иверсона до параллельного scan Блеллоча
Префиксная сумма как общая операция известна под именем 'scan'. Кеннет Айверсон сделал её первоклассной операцией в языке APL ещё в 1962 году в книге 'A Programming Language', записав целые серии накоплений одним символом. В 1990 году Гай Блеллоч в работе 'Prefix Sums and Their Applications' показал, что scan, несмотря на видимую последовательность вычислений, прекрасно распараллеливается и служит строительным блоком для множества параллельных алгоритмов. Сегодня parallel prefix sum встроен в библиотеки GPU вроде CUDA Thrust.
Проблема: много запросов к одним данным
Представь задачу: у тебя есть массив из миллиона чисел, и пользователи постоянно спрашивают "какая сумма элементов с позиции L до позиции R?". Таких запросов - тысячи в секунду.
**Наивный подход**: для каждого запроса проходим от L до R и суммируем.
При 1000 запросах к массиву из миллиона элементов - миллиард операций. Это слишком медленно!
**Ключевое наблюдение**: данные не меняются, а запросов много. Значит, можно **предвычислить** что-то полезное один раз, а потом использовать для быстрых ответов.
Это паттерн 'предвычисление' (preprocessing): потратить время на подготовку, чтобы потом отвечать мгновенно. Trade-off: время подготовки vs время запроса.
**Метафора: книга с оглавлением**
Представь толстую книгу без оглавления. Чтобы найти главу 15, нужно листать с начала. Но если создать оглавление (потратить время один раз), потом любую главу найдёшь за секунды.
Prefix Sum - это 'оглавление' для сумм: мы один раз подсчитаем накопленные суммы, и потом любой запрос - за O(1).
Почему наивный подход плох для множества запросов?
При Q запросах и массиве размера n, общая сложность O(n × Q). Для 1000 запросов к миллиону элементов - миллиард операций.
Идея: накопленные суммы
**Prefix Sum** (префиксная сумма) - массив, где каждый элемент содержит сумму всех предыдущих элементов исходного массива.
**Построение prefix sum:**
**Важно**: prefix имеет длину n+1, и prefix[0] = 0. Это упрощает формулы.
**Как это помогает?** Сумма элементов arr[l..r] = prefix[r+1] - prefix[l].
Почему? prefix[r+1] содержит сумму arr[0..r], а prefix[l] - сумму arr[0..l-1]. Вычитая, получаем arr[l..r].
Формула sum[l..r] = prefix[r+1] - prefix[l] работает потому что мы 'вычитаем' лишний кусок слева.
arr = [2, 5, 1, 3], prefix = [0, 2, 7, 8, 11]. Чему равна сумма arr[1..2]?
sum[1..2] = prefix[3] - prefix[1] = 8 - 2 = 6. Проверка: arr[1] + arr[2] = 5 + 1 = 6 ✓
Реализация и формулы
**Построение prefix sum - O(n):**
**Запрос суммы на отрезке - O(1):**
**Итоговая сложность:**
**Практический пример: подсчёт элементов по условию**
Prefix Sum работает не только для сумм. Можно считать количество элементов, удовлетворяющих условию.
Массив имеет 1000 элементов, и нужно ответить на 10000 запросов суммы на отрезке. Сколько операций потребуется с prefix sum? (ответ в тысячах)
O(n + Q) = 1000 + 10000 = 11000 операций = 11 тысяч. Без prefix sum было бы O(n×Q) = 10 миллионов!
Difference Array: обратная задача
А что если задача обратная? Не много запросов на чтение, а много **обновлений на отрезке**.
**Задача**: добавить значение val ко всем элементам от L до R. Таких операций много, а в конце нужен итоговый массив.
Наивный подход - O(n) на каждое обновление. Но есть трюк: **Difference Array**.
**Идея Difference Array**:
Вместо изменения каждого элемента, мы записываем только **где начинается и где заканчивается** изменение:
**Как это работает?**
diff[i] хранит **изменение** относительно предыдущего элемента. Чтобы получить итоговый массив, вычисляем prefix sum от diff:
Difference Array - это **обратная операция** к Prefix Sum. Prefix Sum суммирует, Difference Array - 'разности'.
**Когда что использовать:**
Чтобы добавить +5 ко всем элементам [2, 5], какие операции нужны в diff array?
diff[l] += val и diff[r+1] -= val. Для [2,5]: diff[2] += 5 и diff[6] -= 5 (индекс r+1 = 5+1 = 6).
2D Prefix Sum: работа с матрицами
Prefix Sum обобщается на двумерный случай - сумма в прямоугольнике матрицы за O(1)!
**Задача**: дана матрица m×n, много запросов "сумма в прямоугольнике от (r1,c1) до (r2,c2)".
**Построение 2D prefix sum:**
prefix[i][j] = сумма всех элементов в прямоугольнике от (0,0) до (i-1, j-1).
**Формула построения** (принцип включения-исключения):
**Визуализация формулы построения:**
**Запрос суммы в прямоугольнике** - тоже принцип включения-исключения:
**Применения 2D Prefix Sum:**
• Подсчёт единиц в области бинарной матрицы
• Поиск подматрицы с максимальной суммой
• Обработка изображений (средняя яркость области)
• Игры (сколько ресурсов в области карты)
Какова сложность построения 2D prefix sum для матрицы m×n?
Мы проходим каждую ячейку один раз, делая O(1) операций. Итого O(m × n).
Итоги
- prefix[i] = сумма первых i элементов
- Сумма [l,r] = prefix[r+1] - prefix[l] за O(1)
- Difference Array: обратная техника для O(1) обновлений
- 2D Prefix Sum использует принцип включения-исключения
Связи с другими темами
Prefix Sum - основа для продвинутых структур данных
- Fenwick Tree — Использует принцип prefix sum
- Segment Tree — Обобщение для произвольных операций
- Скользящее окно — Комбинируется для задач на подотрезках
Связанные уроки
- ds-21-fenwick-tree — Дерево Фенвика добавляет обновления к запросам префиксных сумм
- ds-19-segment-tree — Дерево отрезков обобщает префиксные суммы на динамические диапазоны
- alg-27-sliding-window — Оба отвечают на запросы диапазона за O(1) на шаг
- calc-01-sequences — Префиксная сумма - дискретный аналог интеграла