Beyond Big O

Range sum queries

Range sum queries

Easy

Your 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 1 · empty

Arguments
values
[]
queries
[]
Expected return
[]
Test data
Input
{"values":[],"queries":[]}
Expected output
[]

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]
Editor options
Typing preferences

Saved in this browser.

Restoring local drafts…