Holiday Prefix Sums

Holiday Prefix Sums

As we approach the festive season, many businesses analyze their daily sales to make smart decisions. In this problem, you'll use the prefix sums technique to quickly answer range sum queries over an array of daily sales figures.

Problem Statement

You are given an array of integers arr where each element represents the sales amount on a particular day leading up to the holidays. Additionally, you are given a list of queries. Each query is a pair of integers [L, R] (inclusive) representing the start day and end day respectively. Your task is to implement a function to return a list of sums where each sum is the total sales from day L to day R.

Input

• An array of integers arr of length n.
• A list of queries, where each query is a pair [L, R] (0-indexed).

Output

• Return an array of integers where each element is the sum of arr[L] to arr[R] for the corresponding query.

Example

For example, given the array:

arr = [3, 2, 4, 5, 1]

And queries:

queries = [[1, 3], [0, 4]]

The output should be:

[11, 15]

Explanation:

• The sum of elements from index 1 to 3 is 2 + 4 + 5 = 11.
• The sum of all elements is 3 + 2 + 4 + 5 + 1 = 15.

Requirements

• Use prefix sums to precompute a cumulative sum array for fast query processing.
• Aim to minimize time complexity, especially when the number of queries is large.

Starter Code

Below is some language-agnostic starter code to help you get started with your solution.