noodleProblems/
Range Sum Query - Immutable
#126

Range Sum Query - Immutable

AlgorithmeasyArrayPrefix SumDesign

Given an integer array nums that is never modified, answer a batch of range-sum queries. Each query is a pair [i, j] (0-based, with i <= j) asking for the sum of the elements from index i to index j **inclusive** of both ends.

Return an array whose k-th entry is the answer to the k-th query. Because the array is immutable, the expectation is that you precompute once and then answer every query in constant time.

Example cases

  • overlapping ranges
    in nums = [-2,0,3,-5,2,-1]queries =
    02
    25
    05
    out [1,-1,-3]
    nums[0..2] = -2+0+3 = 1; nums[2..5] = 3-5+2-1 = -1; nums[0..5] = -3.
  • interior range
    in nums = [1,2,3,4]queries =
    13
    out [9]
    nums[1..3] = 2+3+4 = 9.
  • single element
    in nums = [5]queries =
    00
    out [5]
  • no queries
    in nums = [7,8,9], queries = []
    out []

Constraints

  • 0 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= queries.length <= 10^4
  • 0 <= i <= j < nums.length for every query [i, j]
Saved
nums =
[-2,0,3,-5,2,-1]
queries =
[[0,2],[2,5],[0,5]]