Префиксные суммы
Префиксные суммы: ответ на запрос «сумма на отрезке» за O(1); разностный массив.
Ситуация: массив из n чисел и q запросов «чему равна сумма с l-го по r-й элемент?». Считать каждый запрос циклом — O(n·q): при n = q = 10⁵ это 10¹⁰ операций, безнадёжно.
Решение — предподсчёт. Заведём массив префиксных сумм: p[i] = сумма первых i элементов. Тогда сумма на отрезке [l, r] — это просто p[r] - p[l-1]: из «суммы до r» вычли «сумму до l-1». Каждый запрос — O(1), всё вместе — O(n + q).
Введите: 5 2, массив 1 2 3 4 5, затем запросы: 2 4 и 1 5
Детали, которые стоит запомнить:
• индексация с единицы и p[0] = 0 избавляют от особого случая l = 1;
• префиксные суммы копятся в long long — сумма ста тысяч миллиардов в int не влезет;
• та же идея работает в 2D: préfix-таблица позволяет за O(1) отвечать на сумму в прямоугольнике.
Зеркальный приём — разностный массив: если запросы наоборот ИЗМЕНЯЮТ отрезки («прибавить x всем от l до r»), а ответ нужен один раз в конце, храните разности: d[l] += x, d[r+1] -= x, а в конце восстановите массив префиксными суммами самих разностей.
Разностный массив. Введите: 5 2, затем запросы «1 3 2» и «2 5 1»
Задание: по массиву префиксных сумм найдите количество отрезков с нулевой суммой (подсказка: сумма [l, r] нулевая, когда p[r] == p[l-1]; посчитайте одинаковые префиксы через map — это связка двух тем!).
Отметьте урок пройденным и переходите к бинарному поиску.