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

Идея: заранее посчитать массив pre, где pre[i] это сумма всех элементов до i-го включительно. Тогда сумма на отрезке [l, r] это pre[r] - pre[l-1] за O(1) вместо O(n) на каждый запрос.

a = [3, 1, 4, 1, 5, 9]
pre = [0]
for x in a:
    pre.append(pre[-1] + x)

# сумма a[l..r] включительно (0-индексация):
def range_sum(l, r):
    return pre[r + 1] - pre[l]

print(range_sum(1, 3))  # 1+4+1 = 6

Зачем: если запросов на суммы много (например q штук), наивно это O(n*q), а с префиксными суммами O(n + q). Классика для задач, где много раз спрашивают сумму подотрезка.

Считаешь суммы заранее один раз, потом любой отрезок — вычитанием двух чисел.

Сумма отрезка за O(1).