Prefix Sum Queries

Prefix Sums Arrays Queries

Problem Description

Given an array of integers and a list of queries, where each query is a pair of indices [L, R], your task is to compute the sum of the elements between indices L and R (inclusive) for each query. To efficiently answer multiple queries, consider using a prefix sum approach.

Example

For example, given the array arr = [2, 4, 5, 7, 1] and queries [[1, 3], [0, 4]], the answers would be:

  • Query [1, 3]: 4 + 5 + 7 = 16
  • Query [0, 4]: 2 + 4 + 5 + 7 + 1 = 19

Instructions

  1. Compute the prefix sum array from the given array.
  2. Use the prefix sum array to answer each sum query in constant time (O(1)).
  3. Return an array of sums corresponding to each query.

Hint: Remember that the sum between indices L and R can be computed as prefix[R] - prefix[L - 1] (taking care when L is 0).

Today, on December 11, we encourage you to celebrate efficient problem solving skills, much like optimizing approaches in historical algorithm improvements.