Что такое префиксная сумма и как она ускоряет запросы по диапазону?

Question

Accepted Answer

Массив **prefix sum** хранит кумулятивные суммы, так что любую **range sum** можно ответить за **O(1)** после O(n) предварительной обработки — вместо O(n) на запрос.

## Идея

Пусть `prefix[i]` — сумма первых `i` элементов. Тогда сумма `arr[l..r]` равна `prefix[r+1] - prefix[l]`.

## Пример

```python
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
```

## Трассировка

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Сложность

- **Построение:** O(n). **Запрос:** O(1). **Память:** O(n).

## Когда использовать / подводные камни

Идеально для **множественных запросов range-sum** на статических данных. Варианты: 2D prefix sums для сумм подматриц, XOR префиксов и difference arrays для обновлений диапазонов. Если массив часто меняется, используйте вместо этого дерево Фенвика/segment. Следите за смещением индекса (размер n+1).

## Почему это важно

Префиксные суммы превращают повторяющиеся O(n) запросы по диапазону в O(1) поиск — огромная победа, когда запросы частые.

Паттерн однократного предвычисления и быстрого ответа обобщается на многие задачи обработки данных.

Это основной элемент конкурентного программирования и распространённый строительный блок в аналитике.