Range Sum Queries
MediumArrays & Hashing
Problem
A sensor stores one reading per minute in nums. Analysts send a batch of queries, each [l, r], asking for the total of the readings from minute l to minute r inclusive.
Return an array with the answer to each query, in the order the queries were given. Both nums and queries can be large, so answering each query by summing its range is too slow.
Example 1
- Input:
- nums = [3, -2, 5, 1, 4], queries = [[0, 2], [1, 3], [4, 4]]
- Output:
- [6, 4, 4]
3 - 2 + 5 = 6; -2 + 5 + 1 = 4; and the single reading 4.
Example 2
- Input:
- nums = [7], queries = [[0, 0], [0, 0]]
- Output:
- [7, 7]
Constraints
- 1 ≤ nums.length ≤ 10^5
- 0 ≤ queries.length ≤ 10^5
- 0 ≤ l ≤ r < nums.length
- -10^4 ≤ nums[i] ≤ 10^4
Hint
Show the first hint
Many queries share most of their elements. Can you precompute something once?
Walkthrough
How to approach it
01Clarify before coding
- Are ranges inclusive at both ends? Yes.
- Can nums change between queries? No, it is static; with updates you would need a Fenwick tree.
- Can the query list be empty? Yes: return an empty array.
02Brute force
For each query, loop from l to r and add the readings.
Cost: O(n · q) time in the worst case: 10^10 additions for n = q = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.