Массив prefix sum хранит кумулятивные суммы, так что любую range sum можно ответить за O(1) после O(n) предварительной обработки — вместо O(n) на запрос.
Идея
Пусть — сумма первых элементов. Тогда сумма равна .
Массив prefix sum хранит кумулятивные суммы, так что любую range sum можно ответить за O(1) после O(n) предварительной обработки — вместо O(n) на запрос.
Пусть — сумма первых элементов. Тогда сумма равна .
prefix[i]iarr[l..r]prefix[r+1] - prefix[l]def build_prefix(arr):
prefix = [0] * (len(arr) + 1)
for i, x in enumerate(arr):
prefix[i + 1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, l, r): # inclusive l..r
return prefix[r + 1] - prefix[l] # O(1)
p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3) # 4+1+3 -> 8
arr = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
Идеально для множественных запросов range-sum на статических данных. Варианты: 2D prefix sums для сумм подматриц, XOR префиксов и difference arrays для обновлений диапазонов. Если массив часто меняется, используйте вместо этого дерево Фенвика/segment. Следите за смещением индекса (размер n+1).
Префиксные суммы превращают повторяющиеся O(n) запросы по диапазону в O(1) поиск — огромная победа, когда запросы частые.
Паттерн однократного предвычисления и быстрого ответа обобщается на многие задачи обработки данных.
Это основной элемент конкурентного программирования и распространённый строительный блок в аналитике.