Given an integer array nums, handle multiple queries of the following type:
Calculate the sum of the elements of nums between indices left and rightinclusive where left <= right.
Implement the NumArray class:
NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and rightinclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).
We create a prefix sum array $s$ of length $n + 1$, where $s[i]$ represents the prefix sum of the first $i$ elements, that is, $s[i] = \sum_{j=0}^{i-1} nums[j]$. Therefore, the sum of the elements between the indices $[left, right]$ can be expressed as $s[right + 1] - s[left]$.
The time complexity for initializing the prefix sum array $s$ is $O(n)$, and the time complexity for querying is $O(1)$. The space complexity is $O(n)$.
1 2 3 4 5 6 7 8 91011
classNumArray:def__init__(self,nums:List[int]):self.s=list(accumulate(nums,initial=0))defsumRange(self,left:int,right:int)->int:returnself.s[right+1]-self.s[left]# Your NumArray object will be instantiated and called as such:# obj = NumArray(nums)# param_1 = obj.sumRange(left,right)
1 2 3 4 5 6 7 8 9101112131415161718192021
classNumArray{privateint[]s;publicNumArray(int[]nums){intn=nums.length;s=newint[n+1];for(inti=0;i<n;++i){s[i+1]=s[i]+nums[i];}}publicintsumRange(intleft,intright){returns[right+1]-s[left];}}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */
1 2 3 4 5 6 7 8 91011121314151617181920212223
classNumArray{public:NumArray(vector<int>&nums){intn=nums.size();s.resize(n+1);for(inti=0;i<n;++i){s[i+1]=s[i]+nums[i];}}intsumRange(intleft,intright){returns[right+1]-s[left];}private:vector<int>s;};/** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * int param_1 = obj->sumRange(left,right); */
1 2 3 4 5 6 7 8 910111213141516171819202122
typeNumArraystruct{s[]int}funcConstructor(nums[]int)NumArray{n:=len(nums)s:=make([]int,n+1)fori,v:=rangenums{s[i+1]=s[i]+v}returnNumArray{s}}func(this*NumArray)SumRange(leftint,rightint)int{returnthis.s[right+1]-this.s[left]}/** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * param_1 := obj.SumRange(left,right); */
1 2 3 4 5 6 7 8 9101112131415161718192021
classNumArray{privates:number[];constructor(nums:number[]){constn=nums.length;this.s=Array(n+1).fill(0);for(leti=0;i<n;++i){this.s[i+1]=this.s[i]+nums[i];}}sumRange(left:number,right:number):number{returnthis.s[right+1]-this.s[left];}}/** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */
1 2 3 4 5 6 7 8 910111213141516171819202122
structNumArray{s:Vec<i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implNumArray{fnnew(mutnums:Vec<i32>)->Self{letn=nums.len();letmuts=vec![0;n+1];foriin0..n{s[i+1]=s[i]+nums[i];}Self{s}}fnsum_range(&self,left:i32,right:i32)->i32{self.s[(right+1)asusize]-self.s[leftasusize]}}
1 2 3 4 5 6 7 8 910111213141516171819202122232425
/** * @param {number[]} nums */varNumArray=function(nums){constn=nums.length;this.s=Array(n+1).fill(0);for(leti=0;i<n;++i){this.s[i+1]=this.s[i]+nums[i];}};/** * @param {number} left * @param {number} right * @return {number} */NumArray.prototype.sumRange=function(left,right){returnthis.s[right+1]-this.s[left];};/** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(left,right) */
typedefstruct{int*s;}NumArray;NumArray*numArrayCreate(int*nums,intn){int*s=malloc(sizeof(int)*(n+1));s[0]=0;for(inti=0;i<n;i++){s[i+1]=s[i]+nums[i];}NumArray*obj=malloc(sizeof(NumArray));obj->s=s;returnobj;}intnumArraySumRange(NumArray*obj,intleft,intright){returnobj->s[right+1]-obj->s[left];}voidnumArrayFree(NumArray*obj){free(obj->s);free(obj);}/** * Your NumArray struct will be instantiated and called as such: * NumArray* obj = numArrayCreate(nums, numsSize); * int param_1 = numArraySumRange(obj, left, right); * numArrayFree(obj);*/
1 2 3 4 5 6 7 8 9101112131415161718
classNumArray(nums:IntArray){privatevalprefix_sums:IntArrayinit{valnums_size=nums.sizethis.prefix_sums=IntArray(nums_size+1)for(iin0..<nums_size){this.prefix_sums[i+1]=this.prefix_sums[i]+nums[i]}}funsumRange(left:Int,right:Int):Int=this.prefix_sums[right+1]-this.prefix_sums[left]}/** * Your NumArray object will be instantiated and called as such: var obj = NumArray(nums) var * param_1 = obj.sumRange(left,right) */