Given an empty set of intervals, implement a data structure that can:
Add an interval to the set of intervals.
Count the number of integers that are present in at least one interval.
Implement the CountIntervals class:
CountIntervals() Initializes the object with an empty set of intervals.
void add(int left, int right) Adds the interval [left, right] to the set of intervals.
int count() Returns the number of integers that are present in at least one interval.
Note that an interval [left, right] denotes all the integers x where left <= x <= right.
Example 1:
Input
["CountIntervals", "add", "add", "count", "add", "count"]
[[], [2, 3], [7, 10], [], [5, 8], []]
Output
[null, null, null, 6, null, 8]
Explanation
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals.
countIntervals.add(2, 3); // add [2, 3] to the set of intervals.
countIntervals.add(7, 10); // add [7, 10] to the set of intervals.
countIntervals.count(); // return 6
// the integers 2 and 3 are present in the interval [2, 3].
// the integers 7, 8, 9, and 10 are present in the interval [7, 10].
countIntervals.add(5, 8); // add [5, 8] to the set of intervals.
countIntervals.count(); // return 8
// the integers 2 and 3 are present in the interval [2, 3].
// the integers 5 and 6 are present in the interval [5, 8].
// the integers 7 and 8 are present in the intervals [5, 8] and [7, 10].
// the integers 9 and 10 are present in the interval [7, 10].
Constraints:
1 <= left <= right <= 109
At most 105 calls in total will be made to add and count.
classNode:def__init__(self):self.tag=0self.tot=0self.left=Noneself.right=Nonedefupdate(self,l,r,a,b):ifself.tag==1:returnmid=(a+b)>>1ifl==aandr==b:self.tag=1self.tot=b-a+1returnifnotself.left:self.left=Node()ifnotself.right:self.right=Node()ifmid>=l:self.left.update(l,min(mid,r),a,mid)ifmid+1<=r:self.right.update(max(mid+1,l),r,mid+1,b)self.tag=0self.tot=self.left.tot+self.right.totclassCountIntervals:def__init__(self):self.tree=Node()defadd(self,left:int,right:int)->None:self.tree.update(left,right,0,1000000010)defcount(self)->int:returnself.tree.tot# Your CountIntervals object will be instantiated and called as such:# obj = CountIntervals()# obj.add(left,right)# param_2 = obj.count()
classNode{Nodeleft;Noderight;intl;intr;intmid;intv;intadd;publicNode(intl,intr){this.l=l;this.r=r;this.mid=(l+r)>>1;}}classSegmentTree{privateNoderoot=newNode(1,(int)1e9+1);publicSegmentTree(){}publicvoidmodify(intl,intr,intv){modify(l,r,v,root);}publicvoidmodify(intl,intr,intv,Nodenode){if(l>r){return;}if(node.l>=l&&node.r<=r){node.v=node.r-node.l+1;node.add=v;return;}pushdown(node);if(l<=node.mid){modify(l,r,v,node.left);}if(r>node.mid){modify(l,r,v,node.right);}pushup(node);}publicintquery(intl,intr){returnquery(l,r,root);}publicintquery(intl,intr,Nodenode){if(l>r){return0;}if(node.l>=l&&node.r<=r){returnnode.v;}pushdown(node);intv=0;if(l<=node.mid){v+=query(l,r,node.left);}if(r>node.mid){v+=query(l,r,node.right);}returnv;}publicvoidpushup(Nodenode){node.v=node.left.v+node.right.v;}publicvoidpushdown(Nodenode){if(node.left==null){node.left=newNode(node.l,node.mid);}if(node.right==null){node.right=newNode(node.mid+1,node.r);}if(node.add!=0){Nodeleft=node.left,right=node.right;left.add=node.add;right.add=node.add;left.v=left.r-left.l+1;right.v=right.r-right.l+1;node.add=0;}}}classCountIntervals{privateSegmentTreetree=newSegmentTree();publicCountIntervals(){}publicvoidadd(intleft,intright){tree.modify(left,right,1);}publicintcount(){returntree.query(1,(int)1e9);}}/** * Your CountIntervals object will be instantiated and called as such: * CountIntervals obj = new CountIntervals(); * obj.add(left,right); * int param_2 = obj.count(); */
classNode{public:Node(intl,intr):l(l),r(r),mid((l+r)/2),v(0),add(0),left(nullptr),right(nullptr){}intl,r,mid,v,add;Node*left;Node*right;};classSegmentTree{public:SegmentTree():root(newNode(1,1000000001)){}voidmodify(intl,intr,intv,Node*node=nullptr){if(node==nullptr){node=root;}if(l>r){return;}if(node->l>=l&&node->r<=r){node->v=node->r-node->l+1;node->add=v;return;}pushdown(node);if(l<=node->mid){modify(l,r,v,node->left);}if(r>node->mid){modify(l,r,v,node->right);}pushup(node);}intquery(intl,intr,Node*node=nullptr){if(node==nullptr){node=root;}if(l>r){return0;}if(node->l>=l&&node->r<=r){returnnode->v;}pushdown(node);intv=0;if(l<=node->mid){v+=query(l,r,node->left);}if(r>node->mid){v+=query(l,r,node->right);}returnv;}private:Node*root;voidpushup(Node*node){node->v=node->left->v+node->right->v;}voidpushdown(Node*node){if(node->left==nullptr){node->left=newNode(node->l,node->mid);}if(node->right==nullptr){node->right=newNode(node->mid+1,node->r);}if(node->add!=0){Node*left=node->left;Node*right=node->right;left->add=node->add;right->add=node->add;left->v=left->r-left->l+1;right->v=right->r-right->l+1;node->add=0;}}};classCountIntervals{public:CountIntervals(){}voidadd(intleft,intright){tree.modify(left,right,1);}intcount(){returntree.query(1,1000000000);}private:SegmentTreetree;};/** * Your CountIntervals object will be instantiated and called as such: * CountIntervals* obj = new CountIntervals(); * obj->add(left,right); * int param_2 = obj->count(); */
typeNodestruct{left*Noderight*Nodelintrintmidintvintaddint}typeSegmentTreestruct{root*Node}funcnewNode(l,rint)*Node{return&Node{left:nil,right:nil,l:l,r:r,mid:(l+r)/2,v:0,add:0,}}funcnewSegmentTree()*SegmentTree{return&SegmentTree{root:newNode(1,1000000001),}}func(st*SegmentTree)modify(l,r,vint,node*Node){ifnode==nil{node=st.root}ifl>r{return}ifnode.l>=l&&node.r<=r{node.v=node.r-node.l+1node.add=vreturn}st.pushdown(node)ifl<=node.mid{st.modify(l,r,v,node.left)}ifr>node.mid{st.modify(l,r,v,node.right)}st.pushup(node)}func(st*SegmentTree)query(l,rint,node*Node)int{ifnode==nil{node=st.root}ifl>r{return0}ifnode.l>=l&&node.r<=r{returnnode.v}st.pushdown(node)v:=0ifl<=node.mid{v+=st.query(l,r,node.left)}ifr>node.mid{v+=st.query(l,r,node.right)}returnv}func(st*SegmentTree)pushup(node*Node){node.v=node.left.v+node.right.v}func(st*SegmentTree)pushdown(node*Node){ifnode.left==nil{node.left=newNode(node.l,node.mid)}ifnode.right==nil{node.right=newNode(node.mid+1,node.r)}ifnode.add!=0{left:=node.leftright:=node.rightleft.add=node.addright.add=node.addleft.v=left.r-left.l+1right.v=right.r-right.l+1node.add=0}}typeCountIntervalsstruct{tree*SegmentTree}funcConstructor()CountIntervals{returnCountIntervals{tree:newSegmentTree(),}}func(ci*CountIntervals)Add(left,rightint){ci.tree.modify(left,right,1,nil)}func(ci*CountIntervals)Count()int{returnci.tree.query(1,1000000000,nil)}/** * Your CountIntervals object will be instantiated and called as such: * obj := Constructor(); * obj.Add(left,right); * param_2 := obj.Count(); */
classCountIntervals{left:null|CountIntervals;right:null|CountIntervals;start:number;end:number;sum:number;constructor(start:number=0,end:number=10**9){this.left=null;this.right=null;this.start=start;this.end=end;this.sum=0;}add(left:number,right:number):void{if(this.sum==this.end-this.start+1)return;if(left<=this.start&&right>=this.end){this.sum=this.end-this.start+1;return;}letmid=(this.start+this.end)>>1;if(!this.left)this.left=newCountIntervals(this.start,mid);if(!this.right)this.right=newCountIntervals(mid+1,this.end);if(left<=mid)this.left.add(left,right);if(right>mid)this.right.add(left,right);this.sum=this.left.sum+this.right.sum;}count():number{returnthis.sum;}}/** * Your CountIntervals object will be instantiated and called as such: * var obj = new CountIntervals() * obj.add(left,right) * var param_2 = obj.count() */
classNode:__slots__=("left","right","l","r","mid","v","add")def__init__(self,l,r):self.left=Noneself.right=Noneself.l=lself.r=rself.mid=(l+r)//2self.v=0self.add=0classSegmentTree:def__init__(self):self.root=Node(1,int(1e9)+1)defmodify(self,l,r,v,node=None):ifnodeisNone:node=self.rootifl>r:returnifnode.l>=landnode.r<=r:node.v=node.r-node.l+1node.add=vreturnself.pushdown(node)ifl<=node.mid:self.modify(l,r,v,node.left)ifr>node.mid:self.modify(l,r,v,node.right)self.pushup(node)defquery(self,l,r,node=None):ifnodeisNone:node=self.rootifl>r:return0ifnode.l>=landnode.r<=r:returnnode.vself.pushdown(node)v=0ifl<=node.mid:v+=self.query(l,r,node.left)ifr>node.mid:v+=self.query(l,r,node.right)returnvdefpushup(self,node):node.v=node.left.v+node.right.vdefpushdown(self,node):ifnode.leftisNone:node.left=Node(node.l,node.mid)ifnode.rightisNone:node.right=Node(node.mid+1,node.r)ifnode.add!=0:left,right=node.left,node.rightleft.add=node.addright.add=node.addleft.v=left.r-left.l+1right.v=right.r-right.l+1node.add=0classCountIntervals:def__init__(self):self.tree=SegmentTree()defadd(self,left,right):self.tree.modify(left,right,1)defcount(self):returnself.tree.query(1,int(1e9))# Your CountIntervals object will be instantiated and called as such:# obj = CountIntervals()# obj.add(left, right)# param_2 = obj.count()