Range Sum Query - Immutable

Easy~15 min

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

  • NumArray(nums) — Initializes the object with the integer array nums.
  • sumRange(left, right) — Returns the sum of the elements of nums between indices left and right inclusive (i.e., nums[left] + nums[left + 1] + ... + nums[right]).

Examples

Example 1
Input: ["NumArray","sumRange","sumRange","sumRange"] [[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]
Output: [null, 1, -1, -3]
Explanation: NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]); numArray.sumRange(0, 2); // return (-2) + 0 + 3 = 1 numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1 numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3
Example 2
Input: ["NumArray","sumRange"] [[[1]],[0,0]]
Output: [null, 1]
Explanation: NumArray numArray = new NumArray([1]); numArray.sumRange(0, 0); // return 1
Example 3
Input: ["NumArray","sumRange"] [[[1,2,3,4,5]],[0,4]]
Output: [null, 15]
Explanation: NumArray numArray = new NumArray([1, 2, 3, 4, 5]); numArray.sumRange(0, 4); // return 1 + 2 + 3 + 4 + 5 = 15

Constraints

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= left <= right < nums.length
  • At most 10^4 calls will be made to sumRange
  • Expected time complexity: O(1) per query after O(n) preprocessing
Code
Ctrl+EnterRun|Ctrl+⇧+EnterSubmit
Output

Run your code to see results

Use Cmd+Enter to run