# Title: Prefix sums
# Heading: Python Program for Prefix Sums and Range Sum Queries
# Level: intermediate
# Tags: prefix sum, cumulative sum, range sum query, running total
# Time: O(1)
# Space: O(n)
# About: Stores the running totals of a list in one O(n) pass, then answers each range sum query with one subtraction, in O(1).

def prefix_sums(items):
    """sums[i] is the total of the first i items."""
    sums = [0]
    for item in items:
        sums.append(sums[-1] + item)
    return sums


def range_sum(sums, start, stop):
    """The total of items[start:stop]."""
    return sums[stop] - sums[start]


numbers = [4, 7, 2, 9, 5, 3, 8]
sums = prefix_sums(numbers)
print("Prefix sums:", sums)
print("Total of numbers[2:5]:", range_sum(sums, 2, 5))
print("Total of numbers[0:4]:", range_sum(sums, 0, 4))