Shift Totals on Demand

easy

A café logs its hourly sales for the day. The owner keeps asking questions like "what did we make between hour 2 and hour 5?" — dozens of such questions against the same fixed log.

Given sales (one number per hour) and a list of queries where each query is [i, j], return a list with the total sales from hour i through hour j inclusive, one answer per query.

Re-adding the slice for every query is O(n) per question. With many questions, that adds up — precompute something once so each answer costs O(1).

Example 1

in sales = [4, 2, 7, 1, 5], queries = [[1, 3], [0, 4]]

out [10, 19]

Hours 1..3: 2 + 7 + 1 = 10. Hours 0..4: the whole day, 19.

Example 2

in sales = [3], queries = [[0, 0]]

out [3]

Constraints

· 1 <= len(sales) <= 10^5
· 1 <= len(queries) <= 10^5
· 0 <= i <= j < len(sales)
· -10^4 <= sales[h] <= 10^4