If someone asks for many range sums, adding every range from the beginning repeats work. Prefix sums save the total up to every position.
Store what came before
For 2, 4, 1, 3, the running totals are 0, 2, 6, 7, 10. The leading zero makes ranges easier to calculate.
To find the sum from index 1 through index 3, subtract the total before index 1 from the total through index 3: 10 minus 2 equals 8.
- Building the prefix list takes O(n) time.
- Each later range sum takes O(1) time.
- The idea trades extra memory for faster repeated questions.
Build once, ask many times
def make_prefix(numbers):
prefix = [0]
for number in numbers:
prefix.append(prefix[-1] + number)
return prefix
def range_sum(prefix, left, right):
return prefix[right + 1] - prefix[left]
prefix = make_prefix([2, 4, 1, 3])
print(range_sum(prefix, 1, 3)) # 8Prefix information can also store counts, products, or other values that can be safely removed from a larger total.
Your tiny challenge
Build prefix sums for 5, 2, 6, 1. Use two saved totals to find the sum of the middle two numbers.