Given an integer array nums, handle multiple queries of the following types:
Update the value of an element in nums.
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.
void update(int index, int val)Updates the value of nums[index] to be val.
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]).
classBinaryIndexedTree:__slots__=["n","c"]def__init__(self,n):self.n=nself.c=[0]*(n+1)defupdate(self,x:int,delta:int):whilex<=self.n:self.c[x]+=deltax+=x&-xdefquery(self,x:int)->int:s=0whilex>0:s+=self.c[x]x-=x&-xreturnsclassNumArray:__slots__=["tree"]def__init__(self,nums:List[int]):self.tree=BinaryIndexedTree(len(nums))fori,vinenumerate(nums,1):self.tree.update(i,v)defupdate(self,index:int,val:int)->None:prev=self.sumRange(index,index)self.tree.update(index+1,val-prev)defsumRange(self,left:int,right:int)->int:returnself.tree.query(right+1)-self.tree.query(left)# Your NumArray object will be instantiated and called as such:# obj = NumArray(nums)# obj.update(index,val)# param_2 = obj.sumRange(left,right)
classBinaryIndexedTree{privateintn;privateint[]c;publicBinaryIndexedTree(intn){this.n=n;c=newint[n+1];}publicvoidupdate(intx,intdelta){while(x<=n){c[x]+=delta;x+=x&-x;}}publicintquery(intx){ints=0;while(x>0){s+=c[x];x-=x&-x;}returns;}}classNumArray{privateBinaryIndexedTreetree;publicNumArray(int[]nums){intn=nums.length;tree=newBinaryIndexedTree(n);for(inti=0;i<n;++i){tree.update(i+1,nums[i]);}}publicvoidupdate(intindex,intval){intprev=sumRange(index,index);tree.update(index+1,val-prev);}publicintsumRange(intleft,intright){returntree.query(right+1)-tree.query(left);}}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */
classBinaryIndexedTree{public:intn;vector<int>c;BinaryIndexedTree(int_n):n(_n),c(_n+1){}voidupdate(intx,intdelta){while(x<=n){c[x]+=delta;x+=x&-x;}}intquery(intx){ints=0;while(x>0){s+=c[x];x-=x&-x;}returns;}};classNumArray{public:BinaryIndexedTree*tree;NumArray(vector<int>&nums){intn=nums.size();tree=newBinaryIndexedTree(n);for(inti=0;i<n;++i)tree->update(i+1,nums[i]);}voidupdate(intindex,intval){intprev=sumRange(index,index);tree->update(index+1,val-prev);}intsumRange(intleft,intright){returntree->query(right+1)-tree->query(left);}};/** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(index,val); * int param_2 = obj->sumRange(left,right); */
typeBinaryIndexedTreestruct{nintc[]int}funcnewBinaryIndexedTree(nint)*BinaryIndexedTree{c:=make([]int,n+1)return&BinaryIndexedTree{n,c}}func(t*BinaryIndexedTree)update(x,deltaint){for;x<=t.n;x+=x&-x{t.c[x]+=delta}}func(t*BinaryIndexedTree)query(xint)(sint){for;x>0;x-=x&-x{s+=t.c[x]}returns}typeNumArraystruct{tree*BinaryIndexedTree}funcConstructor(nums[]int)NumArray{tree:=newBinaryIndexedTree(len(nums))fori,v:=rangenums{tree.update(i+1,v)}returnNumArray{tree}}func(t*NumArray)Update(indexint,valint){prev:=t.SumRange(index,index)t.tree.update(index+1,val-prev)}func(t*NumArray)SumRange(leftint,rightint)int{returnt.tree.query(right+1)-t.tree.query(left)}/** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * obj.Update(index,val); * param_2 := obj.SumRange(left,right); */
classBinaryIndexedTree{privaten:number;privatec:number[];constructor(n:number){this.n=n;this.c=Array(n+1).fill(0);}update(x:number,delta:number):void{while(x<=this.n){this.c[x]+=delta;x+=x&-x;}}query(x:number):number{lets=0;while(x>0){s+=this.c[x];x-=x&-x;}returns;}}classNumArray{privatetree:BinaryIndexedTree;constructor(nums:number[]){constn=nums.length;this.tree=newBinaryIndexedTree(n);for(leti=0;i<n;++i){this.tree.update(i+1,nums[i]);}}update(index:number,val:number):void{constprev=this.sumRange(index,index);this.tree.update(index+1,val-prev);}sumRange(left:number,right:number):number{returnthis.tree.query(right+1)-this.tree.query(left);}}/** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * obj.update(index,val) * var param_2 = obj.sumRange(left,right) */
classBinaryIndexedTree{privateintn;privateint[]c;publicBinaryIndexedTree(intn){this.n=n;c=newint[n+1];}publicvoidUpdate(intx,intdelta){while(x<=n){c[x]+=delta;x+=x&-x;}}publicintQuery(intx){ints=0;while(x>0){s+=c[x];x-=x&-x;}returns;}}publicclassNumArray{privateBinaryIndexedTreetree;publicNumArray(int[]nums){intn=nums.Length;tree=newBinaryIndexedTree(n);for(inti=0;i<n;++i){tree.Update(i+1,nums[i]);}}publicvoidUpdate(intindex,intval){intprev=SumRange(index,index);tree.Update(index+1,val-prev);}publicintSumRange(intleft,intright){returntree.Query(right+1)-tree.Query(left);}}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.Update(index,val); * int param_2 = obj.SumRange(left,right); */
classNode:__slots__=["l","r","v"]def__init__(self):self.l=self.r=self.v=0classSegmentTree:__slots__=["nums","tr"]def__init__(self,nums):self.nums=numsn=len(nums)self.tr=[Node()for_inrange(n<<2)]self.build(1,1,n)defbuild(self,u,l,r):self.tr[u].l,self.tr[u].r=l,rifl==r:self.tr[u].v=self.nums[l-1]returnmid=(l+r)>>1self.build(u<<1,l,mid)self.build(u<<1|1,mid+1,r)self.pushup(u)defmodify(self,u,x,v):ifself.tr[u].l==xandself.tr[u].r==x:self.tr[u].v=vreturnmid=(self.tr[u].l+self.tr[u].r)>>1ifx<=mid:self.modify(u<<1,x,v)else:self.modify(u<<1|1,x,v)self.pushup(u)defquery(self,u,l,r):ifself.tr[u].l>=landself.tr[u].r<=r:returnself.tr[u].vmid=(self.tr[u].l+self.tr[u].r)>>1result=0ifl<=mid:result+=self.query(u<<1,l,r)ifr>mid:result+=self.query(u<<1|1,l,r)returnresultdefpushup(self,u):self.tr[u].v=self.tr[u<<1].v+self.tr[u<<1|1].vclassNumArray:__slots__=["tree"]def__init__(self,nums:List[int]):self.tree=SegmentTree(nums)defupdate(self,index:int,val:int)->None:self.tree.modify(1,index+1,val)defsumRange(self,left:int,right:int)->int:returnself.tree.query(1,left+1,right+1)# Your NumArray object will be instantiated and called as such:# obj = NumArray(nums)# obj.update(index,val)# param_2 = obj.sumRange(left,right)
classNode{intl;intr;intv;}classSegmentTree{privateNode[]tr;privateint[]nums;publicSegmentTree(int[]nums){this.nums=nums;intn=nums.length;tr=newNode[n<<2];for(inti=0;i<tr.length;++i){tr[i]=newNode();}build(1,1,n);}publicvoidbuild(intu,intl,intr){tr[u].l=l;tr[u].r=r;if(l==r){tr[u].v=nums[l-1];return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}publicvoidmodify(intu,intx,intv){if(tr[u].l==x&&tr[u].r==x){tr[u].v=v;return;}intmid=(tr[u].l+tr[u].r)>>1;if(x<=mid){modify(u<<1,x,v);}else{modify(u<<1|1,x,v);}pushup(u);}publicintquery(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r){returntr[u].v;}intmid=(tr[u].l+tr[u].r)>>1;intv=0;if(l<=mid){v+=query(u<<1,l,r);}if(r>mid){v+=query(u<<1|1,l,r);}returnv;}publicvoidpushup(intu){tr[u].v=tr[u<<1].v+tr[u<<1|1].v;}}classNumArray{privateSegmentTreetree;publicNumArray(int[]nums){tree=newSegmentTree(nums);}publicvoidupdate(intindex,intval){tree.modify(1,index+1,val);}publicintsumRange(intleft,intright){returntree.query(1,left+1,right+1);}}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.update(index,val); * int param_2 = obj.sumRange(left,right); */
classNode{public:intl;intr;intv;};classSegmentTree{public:vector<Node*>tr;vector<int>nums;SegmentTree(vector<int>&nums){this->nums=nums;intn=nums.size();tr.resize(n<<2);for(inti=0;i<tr.size();++i)tr[i]=newNode();build(1,1,n);}voidbuild(intu,intl,intr){tr[u]->l=l;tr[u]->r=r;if(l==r){tr[u]->v=nums[l-1];return;}intmid=(l+r)>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);}voidmodify(intu,intx,intv){if(tr[u]->l==x&&tr[u]->r==x){tr[u]->v=v;return;}intmid=(tr[u]->l+tr[u]->r)>>1;if(x<=mid)modify(u<<1,x,v);elsemodify(u<<1|1,x,v);pushup(u);}intquery(intu,intl,intr){if(tr[u]->l>=l&&tr[u]->r<=r)returntr[u]->v;intmid=(tr[u]->l+tr[u]->r)>>1;intv=0;if(l<=mid)v+=query(u<<1,l,r);if(r>mid)v+=query(u<<1|1,l,r);returnv;}voidpushup(intu){tr[u]->v=tr[u<<1]->v+tr[u<<1|1]->v;}};classNumArray{public:SegmentTree*tree;NumArray(vector<int>&nums){tree=newSegmentTree(nums);}voidupdate(intindex,intval){returntree->modify(1,index+1,val);}intsumRange(intleft,intright){returntree->query(1,left+1,right+1);}};/** * Your NumArray object will be instantiated and called as such: * NumArray* obj = new NumArray(nums); * obj->update(index,val); * int param_2 = obj->sumRange(left,right); */
typeNodestruct{l,r,vint}typeSegmentTreestruct{tr[]Nodenums[]int}funcnewSegmentTree(nums[]int)*SegmentTree{n:=len(nums)tr:=make([]Node,n<<2)fori:=rangetr{tr[i]=Node{}}tree:=&SegmentTree{tr:tr,nums:nums,}tree.build(1,1,n)returntree}func(tree*SegmentTree)build(u,l,rint){tree.tr[u].l,tree.tr[u].r=l,rifl==r{tree.tr[u].v=tree.nums[l-1]return}mid:=(l+r)>>1tree.build(u<<1,l,mid)tree.build(u<<1|1,mid+1,r)tree.pushup(u)}func(tree*SegmentTree)modify(u,x,vint){iftree.tr[u].l==x&&tree.tr[u].r==x{tree.tr[u].v=vreturn}mid:=(tree.tr[u].l+tree.tr[u].r)>>1ifx<=mid{tree.modify(u<<1,x,v)}else{tree.modify(u<<1|1,x,v)}tree.pushup(u)}func(tree*SegmentTree)query(u,l,rint)(vint){iftree.tr[u].l>=l&&tree.tr[u].r<=r{returntree.tr[u].v}mid:=(tree.tr[u].l+tree.tr[u].r)>>1ifl<=mid{v+=tree.query(u<<1,l,r)}ifr>mid{v+=tree.query(u<<1|1,l,r)}returnv}func(tree*SegmentTree)pushup(uint){tree.tr[u].v=tree.tr[u<<1].v+tree.tr[u<<1|1].v}typeNumArraystruct{tree*SegmentTree}funcConstructor(nums[]int)NumArray{returnNumArray{tree:newSegmentTree(nums),}}func(this*NumArray)Update(indexint,valint){this.tree.modify(1,index+1,val)}func(this*NumArray)SumRange(leftint,rightint)int{returnthis.tree.query(1,left+1,right+1)}/** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * obj.Update(index,val); * param_2 := obj.SumRange(left,right); */
classNode{l:number;r:number;v:number;}classSegmentTree{privatetr:Node[];privatenums:number[];constructor(nums:number[]){this.nums=nums;constn=nums.length;this.tr=newArray<Node>(n<<2);for(leti=0;i<this.tr.length;++i){this.tr[i]={l:0,r:0,v:0};}this.build(1,1,n);}build(u:number,l:number,r:number):void{this.tr[u].l=l;this.tr[u].r=r;if(l==r){this.tr[u].v=this.nums[l-1];return;}constmid=(l+r)>>1;this.build(u<<1,l,mid);this.build((u<<1)|1,mid+1,r);this.pushup(u);}modify(u:number,x:number,v:number):void{if(this.tr[u].l==x&&this.tr[u].r==x){this.tr[u].v=v;return;}constmid=(this.tr[u].l+this.tr[u].r)>>1;if(x<=mid){this.modify(u<<1,x,v);}else{this.modify((u<<1)|1,x,v);}this.pushup(u);}query(u:number,l:number,r:number):number{if(this.tr[u].l>=l&&this.tr[u].r<=r){returnthis.tr[u].v;}constmid=(this.tr[u].l+this.tr[u].r)>>1;letv=0;if(l<=mid){v+=this.query(u<<1,l,r);}if(r>mid){v+=this.query((u<<1)|1,l,r);}returnv;}pushup(u:number):void{this.tr[u].v=this.tr[u<<1].v+this.tr[(u<<1)|1].v;}}classNumArray{privatetree:SegmentTree;constructor(nums:number[]){this.tree=newSegmentTree(nums);}update(index:number,val:number):void{this.tree.modify(1,index+1,val);}sumRange(left:number,right:number):number{returnthis.tree.query(1,left+1,right+1);}}/** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * obj.update(index,val) * var param_2 = obj.sumRange(left,right) */
publicclassNode{publicintl;publicintr;publicintv;}publicclassSegmentTree{privateNode[]tr;privateint[]nums;publicSegmentTree(int[]nums){this.nums=nums;intn=nums.Length;tr=newNode[n<<2];for(inti=0;i<tr.Length;++i){tr[i]=newNode();}Build(1,1,n);}publicvoidBuild(intu,intl,intr){tr[u].l=l;tr[u].r=r;if(l==r){tr[u].v=nums[l-1];return;}intmid=(l+r)>>1;Build(u<<1,l,mid);Build(u<<1|1,mid+1,r);Pushup(u);}publicvoidModify(intu,intx,intv){if(tr[u].l==x&&tr[u].r==x){tr[u].v=v;return;}intmid=(tr[u].l+tr[u].r)>>1;if(x<=mid){Modify(u<<1,x,v);}else{Modify(u<<1|1,x,v);}Pushup(u);}publicintQuery(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r){returntr[u].v;}intmid=(tr[u].l+tr[u].r)>>1;intv=0;if(l<=mid){v+=Query(u<<1,l,r);}if(r>mid){v+=Query(u<<1|1,l,r);}returnv;}publicvoidPushup(intu){tr[u].v=tr[u<<1].v+tr[u<<1|1].v;}}publicclassNumArray{privateSegmentTreetree;publicNumArray(int[]nums){tree=newSegmentTree(nums);}publicvoidUpdate(intindex,intval){tree.Modify(1,index+1,val);}publicintSumRange(intleft,intright){returntree.Query(1,left+1,right+1);}}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * obj.Update(index,val); * int param_2 = obj.SumRange(left,right); */