Алгоритмы trainee
Что такое префиксная сумма?
Ответ
Массив, где prefix[i] = sum(arr[0..i]). Позволяет за O(1) узнать сумму на отрезке [l..r]: sum(l..r) = prefix[r] - prefix[l-1]. Полезно когда много запросов сумм на разных отрезках одного массива.
Разбор: Префиксная сумма — это массив, где prefix[i] хранит сумму всех элементов с 0 по i, что даёт сумму отрезка за O(1) как prefix[r] - prefix[l-1]. Ловушки: prefix[i] — накопительная сумма от начала, а не сумма пар; вычитать нужно prefix[l-1] (а не prefix[l]); и структура считает суммы, а не максимумы (для максимума нужны разреженные таблицы или деревья).
Хочешь так же по своей компании — с вопросами по грейдам и задачами? Закажи гайд или забери свежее в Telegram.