Question
Formatted question description: https://leetcode.ca/all/303.html
303 Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
@tag-array
Algorithm
Establish a cumulative sum array dp, where dp[i]
represents the sum of the numbers in the interval [0, i]
, then [i,j]
can be expressed as dp[j]-dp[i-1]
, pay attention here When i=0, just return dp[j]
directly.
Code
Java
-
public class Range_Sum_Query_Immutable { class NumArray { private int[] sum; public NumArray(int[] nums) { sum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { // sum x meaning sumup until index x-1 sum[i + 1] = sum[i] + nums[i]; } } public int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } } /** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(i,j); */ }
-
class NumArray { public: NumArray(vector<int> &nums) { dp.resize(nums.size() + 1, 0); for (int i = 1; i <= nums.size(); ++i) { dp[i] = dp[i - 1] + nums[i - 1]; } } int sumRange(int i, int j) { return dp[j + 1] - dp[i]; } private: vector<int> dp; };
-
class NumArray(object): def __init__(self, nums): """ initialize your data structure here. :type nums: List[int] """ self.dp = [0] * (len(nums) + 1) for i in range(0, len(nums)): self.dp[i + 1] = self.dp[i] + nums[i] def sumRange(self, i, j): """ sum of elements nums[i..j], inclusive. :type i: int :type j: int :rtype: int """ return self.dp[j + 1] - self.dp[i] # Your NumArray object will be instantiated and called as such: # numArray = NumArray(nums) # numArray.sumRange(0, 1) # numArray.sumRange(1, 2)