Prefix Sum Queries

Problem: Prefix Sum Queries

Given an array of integers and a list of queries, each query consists of two indices (start and end). Your task is to precompute a prefix sum array from the given array so that each query can be answered in constant time.

Instructions:

• Input:

  • An array of integers. For example: [3, 2, 4, 5, 1].
  • A list of queries where each query is a pair of indices [start, end] (0-indexed). For example: [[1, 3], [0, 2]].

• Output:

  • For each query, return the sum of the subarray from index start to index end (inclusive).

Example:

Input:

array = [3, 2, 4, 5, 1]
queries = [[1, 3], [0, 2]]

Output:

[11, 9]

Explanation:

• For the query [1, 3], the subarray is [2, 4, 5] whose sum is 11.
• For the query [0, 2], the subarray is [3, 2, 4] whose sum is 9.

Try to think about how you could quickly answer each query after a one-time precomputation of the prefix sum array. Given that today's date is November 2nd, a day of remembrance (All Souls' Day), consider how even small improvements (like efficient query responses) can save time for tasks that you might face every day.

Starter Code:

Below is some starter code in multiple programming languages to get you started.