Example 1 · empty
- Arguments
- values
[]
queries[]
- Expected return
[]
Test data
- Input
{"values":[],"queries":[]}- Expected output
[]
Range sum queries
Range sum queries
EasyYour task
- You have a list of values and several ranges to total.
- Return one sum per query, in the same order as the queries.
Required API
- RangeSums
func RangeSums(values []int, queries [][2]int) []int
Behavior
- A query [start, end] means the half-open range [start, end): include values[start] through values[end - 1], but not values[end].
- An empty range sums to 0.
- No queries means an empty result list.
- Do not change values or queries.
- Separate calls are independent.
- Aim for O(n + q) total time for n values and q queries, using only the standard library.
- Explain how preprocessing avoids rescanning each range.
Constraints
- The input is valid: values contains 0–1,000 integers between -100,000 and 100,000 inclusive.
- There are 0–500 queries, each a pair of integer indices satisfying 0 <= start <= end <= len(values).
- The end index may equal len(values).
- Sums fit between -100,000,000 and 100,000,000 inclusive.
Notes and example notation
Examples use {"values": [...], "queries": [[start, end], ...]}.
Examples
The runner calls your functions directly; you do not need to parse JSON.
Example 2 · mixed ranges
- Arguments
- values
[ 4, -2, 7, 1 ]
queries[ [ 0, 4 ], [ 1, 3 ], [ 2, 2 ] ] - Expected return
[ 10, 5, 0 ]
Test data
- Input
{"values":[4,-2,7,1],"queries":[[0,4],[1,3],[2,2]]}- Expected output
[10,5,0]
Example 3 · empty ranges
- Arguments
- values
[]
queries[ [ 0, 0 ], [ 0, 0 ] ] - Expected return
[ 0, 0 ]
Test data
- Input
{"values":[],"queries":[[0,0],[0,0]]}- Expected output
[0,0]
Example 4 · repeated
- Arguments
- values
[ -3, 5, -1 ]
queries[ [ 1, 3 ], [ 0, 1 ], [ 1, 3 ] ] - Expected return
[ 4, -3, 4 ]
Test data
- Input
{"values":[-3,5,-1],"queries":[[1,3],[0,1],[1,3]]}- Expected output
[4,-3,4]
Solution guide
Reveal solution guide — spoilers
Approach
- Build a prefix array of length n + 1 with prefix[0] = 0 and prefix[i + 1] = prefix[i] + values[i].
- For each query [start, end], append prefix[end] - prefix[start] to the result in query order.
- Use the supplied half-open boundaries directly. Do not decrement end or rescan each range, and leave values and queries unchanged.
Why it works
prefix[end] totals exactly the values before end. Subtracting prefix[start] removes the values before start, leaving precisely indices start through end - 1. The leading zero makes ranges starting at zero and empty ranges obey the same formula.
Complexity
O(n + q) total time for n values and q queries, with O(n) auxiliary prefix storage excluding the O(q) returned sums. Use an integer type covering the stated sum bounds.
Edge cases to check
- A query with start equal to end sums to zero, including [n, n].
- end may equal len(values), which is a valid prefix index.
- No queries produces an empty result; empty values permit only empty ranges. Negative values require no special-case adjustment.
Restoring local drafts…
Checking execution availability…
Public examples
NO CODE EXECUTEDExplore the examples.
View inputs and expected outputs. Examples do not run your code.