Префиксные суммы

Условие

Дан массив из n чисел и q запросов вида «сумма элементов с l по r включительно».

Идея

Заранее считаем p[k] — сумму первых k элементов, p[0] = 0. Тогда сумма на отрезке — разность двух префиксов: p[r + 1] - p[l].

from itertools import accumulate

def build(a):
    return [0, *accumulate(a)]

def range_sum(p, l, r):
    return p[r + 1] - p[l]

Подготовка O(n), каждый запрос O(1).