Префиксные суммы — заранее посчитанные суммы первых i элементов массива. Одна подготовка за O(n) позволяет получать сумму любого отрезка за O(1). Обратная идея, разностный массив, делает массовое обновление отрезка за O(1).

![Сумма a[2..5] равна P[6] - P[2] = 19](img/lessons/algorithms/prefix-sums-range-query.svg)

Префиксный массив и запрос на отрезке

По определению prefix[0] = 0, prefix[i] = a[0] + ... + a[i-1]. Сумма a[l..r] (оба конца включительно) равна prefix[r + 1] - prefix[l]: разность вычитает a[0..l-1] из a[0..r]. Нуль в начале убирает особый случай для левой границы (l = 0). Для подготовки хватает itertools.accumulate.

python
from itertools import accumulate

a = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0] + list(accumulate(a))   # prefix[i] = sum(a[:i])

def range_sum(l, r):                 # inclusive bounds
    return prefix[r + 1] - prefix[l]

print(prefix)
print(range_sum(2, 5), range_sum(0, 7), range_sum(3, 3))