All problems

Honey Stretch Totals

Easy · prefix sum

Mira keeps bees. Every evening she weighs the honey her hive gave that day and writes the number down. The list honey holds these weights in order, so honey[0] is day 1, honey[1] is day 2, and so on.

Visitors keep asking her the same kind of question: "How much honey did you collect from day 4 to day 9?" Each question is a pair starts[i] and ends[i]: the first and last day of a stretch, both included. Day numbers start at 1.

Return a list with the total honey of every stretch, in the same order as the questions.

Examples

Example 1

Input: honey = [3, 1, 4, 1, 5], starts = [1, 2, 5], ends = [3, 4, 5]

Output: [8, 6, 5]

Days 1 to 3 give 3 + 1 + 4 = 8, days 2 to 4 give 1 + 4 + 1 = 6, and day 5 alone gives 5.

Example 2

Input: honey = [0, 0, 7], starts = [1, 3], ends = [2, 3]

Output: [0, 7]

Constraints

• 1 <= len(honey) <= 10^5
• 0 <= honey[i] <= 1000
• 1 <= len(starts) <= 10^5
• len(ends) == len(starts)
• 1 <= starts[i] <= ends[i] <= len(honey)