Problem 357170 · easy · Phase 03 Linear Management & Searching

Range Sum Queries

prefix sums · classes

If you must answer many "what is the sum of elements from index left to right?" questions, adding them up each time is O(n) per query. A prefix sum array lets you precompute once and answer each query in O(1).

Implement a class NumArray:

  • NumArray(nums) — the constructor receives the list of integers.
  • sum_range(left, right) — returns the sum of nums[left] + nums[left+1] + ... + nums[right] (both ends inclusive).

Examples

Input:
  NumArray([-2, 0, 3, -5, 2, -1])
  sum_range(0, 2)   -> 1     (-2 + 0 + 3)
  sum_range(2, 5)   -> -1    (3 - 5 + 2 - 1)
  sum_range(0, 5)   -> -3

Constraints

  • 1 <= len(nums) <= 10**4
  • 0 <= left <= right < len(nums)
  • The constructor may do O(n) work; aim for O(1) per sum_range call.

Goals

  • Build a prefix-sum array in the constructor so queries become O(1)
  • Express the sum of nums[left..right] as a difference of two prefix sums
  • Handle the off-by-one at the left edge with a leading 0
Starting Python…