Prefix sums are precomputed sums of the first i elements of an array. One O(n) preparation gives the sum of any range in O(1). The inverse idea, the difference array, applies a range update in O(1).

![The sum of a[2..5] equals P[6] - P[2] = 19](img/lessons/algorithms/prefix-sums-range-query.svg)

The prefix array and a range query

By definition prefix[0] = 0, prefix[i] = a[0] + ... + a[i-1]. The sum of a[l..r] (both ends inclusive) is prefix[r + 1] - prefix[l], since the difference subtracts a[0..l-1] from a[0..r]. The leading 0 removes a special case for the left boundary (l = 0). itertools.accumulate is enough to prepare it.

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))