Arrays and Hashing Prefix sums
76. Range Sum Query - Immutable
You are given an array of integers nums and a list of queries. Each query is a pair [left, right] and
asks for the sum of the elements of nums from index left to index right, both ends included.
Return an array answer with one entry per query, in the order the queries are given: answer[j] is the
sum that queries[j] asks for.
Example 1
Input: nums = [3, -2, 5, 1, -4, 6]
queries = [[0, 2], [1, 4], [3, 3], [0, 5]]
[6,0,1,9]Explanation: [0, 2] covers 3, −2 and 5, which add up to 6. [1, 4] covers −2, 5, 1 and −4, which add up to 0.
[3, 3] is the single element 1, and [0, 5] is the whole array, which adds up to 9.
Example 2
Input: nums = [-7, -7, -7]
queries = [[2, 2], [0, 2], [0, 2], [0, 0]]
[-7,-21,-21,-7]Explanation: The query [0, 2] appears twice, and each copy gets its own answer. The queries do not come in any
particular order.
Example 3
Input: nums = [1000000000, 1000000000, 1000000000]
queries = [[0, 2], [1, 2], [0, 0]]
[3000000000,2000000000,1000000000]Explanation: The first sum is 3 × 109, which is more than a 32-bit integer can hold.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 1091 ≤ queries.length ≤ 105queries[j] = [left, right]0 ≤ left ≤ right < nums.length
Clarifying questions
What you would ask an interviewer before writing any code.