#201EasyPrefix Sums & Difference Arrays· Prefix Sums for Range Queries

Sales Range Totals

A bakery records how many loaves it sold on each day of the year. The owner keeps asking questions such as "how many loaves did we sell between day 40 and day 75?" and wants every answer immediately, even though there are many questions. You are given the daily sales as an array `sales` and a list of `queries`. Each query is a pair `[l, r]` of 0-based day indexes (both inclusive). For every query, return the total of `sales[l..r]`. Answers must be returned in the order of the queries. Adding up the days for every query separately is too slow when there are many long queries, so do some work once up front.

Input format

`sales`: the daily sales. `queries`: a list of `[l, r]` pairs.

Output format

An array with one total per query, in query order.

Examples

Input: sales = [4, 2, 7, 1, 3], queries = [[0, 4], [1, 2], [3, 3]]

Output: [17, 9, 1]

The whole week sums to 17, days 1 and 2 give 2 + 7 = 9, and day 3 alone is 1.

Input: sales = [5, -2, -3, 8], queries = [[1, 2], [0, 3]]

Output: [-5, 8]

Days 1 and 2 are -2 and -3 so the total is -5; all four days give 5 - 2 - 3 + 8 = 8.

Constraints

1 <= sales.length <= 10^5
-10^4 <= sales[i] <= 10^4 (a negative value is a day with more returns than sales)
1 <= queries.length <= 10^5
0 <= l <= r < sales.length

#prefix-sums
#arrays
#range-queries
#precomputation