Problem
Imagine you are designing a data analysis tool that allows users to swiftly calculate the sum of values within specified segments of a dataset. You are provided with an array of integers, representing data points, and a series of queries. Each query defines a range in the array, and your task is to efficiently compute the sum of the elements within these ranges. This can be achieved by using the concept of prefix sums. Prefix sums involve precomputing the cumulative sums of the array, allowing you to quickly retrieve the sum for any range by subtracting the cumulative sum up to the start of the range from the cumulative sum up to the end of the range. To tackle this problem, first compute the prefix sum array where each element at index 'i' is the sum of all elements from the start of the array up to 'i'. For each query, use the prefix sums to calculate the sum of elements between the start and end indices efficiently. For example, if your array is [1, 2, 3, 4, 5] and a query asks for the sum from index 1 to 3, the prefix sums help you quickly find the answer: 2 + 3 + 4 = 9. Consider edge cases such as empty ranges or when the range covers the entire array. Ensure your solution handles large input sizes efficiently.
- Approach the problem by first building a prefix sum array.
- Consider leveraging the prefix sum to avoid recalculating sums from scratch for each query.
- Think about how to handle edge cases, such as when the start index is zero.
- Optimization tip: Once the prefix sum array is built, each range query can be answered in constant time.
Input format
The first line contains two integers n and q (1 <= n, q <= 1000), where n is the number of elements in the array, and q is the number of queries. The second line contains n space-separated integers representing the array. The next q lines each contain two integers l and r (0 <= l <= r < n) representing the range indices for the query.
Output format
For each query, output the sum of the elements from index l to r, inclusive, on a new line.
Constraints
1 <= array[i] <= 10^4
Sample input
5 3 1 2 3 4 5 1 3 0 4 2 2
Sample output
9 15 3