A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.
A half-open interval[left, right) denotes all the real numbers x where left <= x < right.
Implement the RangeModule class:
RangeModule() Initializes the object of the data structure.
void addRange(int left, int right) Adds the half-open interval[left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval[left, right).
Example 1:
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]
Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
Constraints:
1 <= left < right <= 109
At most 104 calls will be made to addRange, queryRange, and removeRange.
Solutions
Solution 1: Segment Tree
According to the problem description, we need to maintain a set of intervals, supporting operations of interval addition, deletion, and query. For the addition and deletion of intervals, we can use a segment tree to maintain the set of intervals.
The segment tree divides the entire interval into multiple non-continuous sub-intervals, the number of which does not exceed $\log(width)$. To update the value of an element, only $\log(width)$ intervals need to be updated, and these intervals are all included in a large interval containing the element. When modifying the interval, we need to use lazy propagation to ensure efficiency.
Each node of the segment tree represents an interval;
The segment tree has a unique root node, representing the entire statistical range, such as $[1,N]$;
Each leaf node of the segment tree represents an elementary interval of length $1$, $[x,x]$;
For each internal node $[l,r]$, its left child is $[l,mid]$, and the right child is $[mid+1,r]$, where $mid=β(l+r)/2β$ (rounded down).
Due to the large data range of the problem, we can implement it with a dynamically allocated segment tree. A dynamically allocated segment tree means that we only allocate nodes when needed, instead of allocating all nodes at the beginning. This can save space, but it requires lazy propagation to maintain interval modification.
In terms of time complexity, the time complexity of each operation is $O(\log n)$. The space complexity is $O(m \times \log n)$. Here, $m$ is the number of operations, and $n$ is the data range.
classNode:__slots__=['left','right','add','v']def__init__(self):self.left=Noneself.right=Noneself.add=0self.v=FalseclassSegmentTree:__slots__=['root']def__init__(self):self.root=Node()defmodify(self,left,right,v,l=1,r=int(1e9),node=None):ifnodeisNone:node=self.rootifl>=leftandr<=right:ifv==1:node.add=1node.v=Trueelse:node.add=-1node.v=Falsereturnself.pushdown(node)mid=(l+r)>>1ifleft<=mid:self.modify(left,right,v,l,mid,node.left)ifright>mid:self.modify(left,right,v,mid+1,r,node.right)self.pushup(node)defquery(self,left,right,l=1,r=int(1e9),node=None):ifnodeisNone:node=self.rootifl>=leftandr<=right:returnnode.vself.pushdown(node)mid=(l+r)>>1v=Trueifleft<=mid:v=vandself.query(left,right,l,mid,node.left)ifright>mid:v=vandself.query(left,right,mid+1,r,node.right)returnvdefpushup(self,node):node.v=bool(node.leftandnode.left.vandnode.rightandnode.right.v)defpushdown(self,node):ifnode.leftisNone:node.left=Node()ifnode.rightisNone:node.right=Node()ifnode.add:node.left.add=node.right.add=node.addnode.left.v=node.add==1node.right.v=node.add==1node.add=0classRangeModule:def__init__(self):self.tree=SegmentTree()defaddRange(self,left:int,right:int)->None:self.tree.modify(left,right-1,1)defqueryRange(self,left:int,right:int)->bool:returnself.tree.query(left,right-1)defremoveRange(self,left:int,right:int)->None:self.tree.modify(left,right-1,-1)# Your RangeModule object will be instantiated and called as such:# obj = RangeModule()# obj.addRange(left,right)# param_2 = obj.queryRange(left,right)# obj.removeRange(left,right)
classNode{Nodeleft;Noderight;intadd;booleanv;}classSegmentTree{privateNoderoot=newNode();publicSegmentTree(){}publicvoidmodify(intleft,intright,intv){modify(left,right,v,1,(int)1e9,root);}publicvoidmodify(intleft,intright,intv,intl,intr,Nodenode){if(l>=left&&r<=right){node.v=v==1;node.add=v;return;}pushdown(node);intmid=(l+r)>>1;if(left<=mid){modify(left,right,v,l,mid,node.left);}if(right>mid){modify(left,right,v,mid+1,r,node.right);}pushup(node);}publicbooleanquery(intleft,intright){returnquery(left,right,1,(int)1e9,root);}publicbooleanquery(intleft,intright,intl,intr,Nodenode){if(l>=left&&r<=right){returnnode.v;}pushdown(node);intmid=(l+r)>>1;booleanv=true;if(left<=mid){v=v&&query(left,right,l,mid,node.left);}if(right>mid){v=v&&query(left,right,mid+1,r,node.right);}returnv;}publicvoidpushup(Nodenode){node.v=node.left!=null&&node.left.v&&node.right!=null&&node.right.v;}publicvoidpushdown(Nodenode){if(node.left==null){node.left=newNode();}if(node.right==null){node.right=newNode();}if(node.add!=0){node.left.add=node.add;node.right.add=node.add;node.left.v=node.add==1;node.right.v=node.add==1;node.add=0;}}}classRangeModule{privateSegmentTreetree=newSegmentTree();publicRangeModule(){}publicvoidaddRange(intleft,intright){tree.modify(left,right-1,1);}publicbooleanqueryRange(intleft,intright){returntree.query(left,right-1);}publicvoidremoveRange(intleft,intright){tree.modify(left,right-1,-1);}}/** * Your RangeModule object will be instantiated and called as such: * RangeModule obj = new RangeModule(); * obj.addRange(left,right); * boolean param_2 = obj.queryRange(left,right); * obj.removeRange(left,right); */
template<classT>classCachedObj{public:void*operatornew(size_ts){if(!head){T*a=newT[SIZE];for(size_ti=0;i<SIZE;++i)add(a+i);}T*p=head;head=head->CachedObj<T>::next;returnp;}voidoperatordelete(void*p,size_t){if(p)add(static_cast<T*>(p));}virtual~CachedObj(){}protected:T*next;private:staticT*head;staticconstsize_tSIZE;staticvoidadd(T*p){p->CachedObj<T>::next=head;head=p;}};template<classT>T*CachedObj<T>::head=0;template<classT>constsize_tCachedObj<T>::SIZE=10000;classNode:publicCachedObj<Node>{public:Node*left;Node*right;intadd;boolv;};classSegmentTree{private:Node*root;public:SegmentTree(){root=newNode();}voidmodify(intleft,intright,intv){modify(left,right,v,1,1e9,root);}voidmodify(intleft,intright,intv,intl,intr,Node*node){if(l>=left&&r<=right){node->v=v==1;node->add=v;return;}pushdown(node);intmid=(l+r)>>1;if(left<=mid)modify(left,right,v,l,mid,node->left);if(right>mid)modify(left,right,v,mid+1,r,node->right);pushup(node);}boolquery(intleft,intright){returnquery(left,right,1,1e9,root);}boolquery(intleft,intright,intl,intr,Node*node){if(l>=left&&r<=right)returnnode->v;pushdown(node);intmid=(l+r)>>1;boolv=true;if(left<=mid)v=v&&query(left,right,l,mid,node->left);if(right>mid)v=v&&query(left,right,mid+1,r,node->right);returnv;}voidpushup(Node*node){node->v=node->left&&node->left->v&&node->right&&node->right->v;}voidpushdown(Node*node){if(!node->left)node->left=newNode();if(!node->right)node->right=newNode();if(node->add){node->left->add=node->right->add=node->add;node->left->v=node->right->v=node->add==1;node->add=0;}}};classRangeModule{public:SegmentTree*tree;RangeModule(){tree=newSegmentTree();}voidaddRange(intleft,intright){tree->modify(left,right-1,1);}boolqueryRange(intleft,intright){returntree->query(left,right-1);}voidremoveRange(intleft,intright){tree->modify(left,right-1,-1);}};/** * Your RangeModule object will be instantiated and called as such: * RangeModule* obj = new RangeModule(); * obj->addRange(left,right); * bool param_2 = obj->queryRange(left,right); * obj->removeRange(left,right); */
constNint=1e9typenodestruct{lch*noderch*nodeaddedboollazyint}typesegmentTreestruct{root*node}funcnewSegmentTree()*segmentTree{return&segmentTree{root:new(node),}}func(t*segmentTree)update(n*node,l,r,i,j,xint){ifl>=i&&r<=j{n.added=x==1n.lazy=xreturn}t.pushdown(n)m:=int(uint(l+r)>>1)ifi<=m{t.update(n.lch,l,m,i,j,x)}ifj>m{t.update(n.rch,m+1,r,i,j,x)}t.pushup(n)}func(t*segmentTree)query(n*node,l,r,i,jint)bool{ifl>=i&&r<=j{returnn.added}t.pushdown(n)v:=truem:=int(uint(l+r)>>1)ifi<=m{v=v&&t.query(n.lch,l,m,i,j)}ifj>m{v=v&&t.query(n.rch,m+1,r,i,j)}returnv}func(t*segmentTree)pushup(n*node){n.added=n.lch.added&&n.rch.added}func(t*segmentTree)pushdown(n*node){ifn.lch==nil{n.lch=new(node)}ifn.rch==nil{n.rch=new(node)}ifn.lazy!=0{n.lch.added=n.lazy==1n.rch.added=n.lazy==1n.lch.lazy=n.lazyn.rch.lazy=n.lazyn.lazy=0}}typeRangeModulestruct{t*segmentTree}funcConstructor()RangeModule{returnRangeModule{t:newSegmentTree(),}}func(this*RangeModule)AddRange(leftint,rightint){this.t.update(this.t.root,1,N,left,right-1,1)}func(this*RangeModule)QueryRange(leftint,rightint)bool{returnthis.t.query(this.t.root,1,N,left,right-1)}func(this*RangeModule)RemoveRange(leftint,rightint){this.t.update(this.t.root,1,N,left,right-1,-1)}/** * Your RangeModule object will be instantiated and called as such: * obj := Constructor(); * obj.AddRange(left,right); * param_2 := obj.QueryRange(left,right); * obj.RemoveRange(left,right); */
classNode{left:Node|null;right:Node|null;add:number;v:boolean;constructor(){this.left=null;this.right=null;this.add=0;this.v=false;}}classSegmentTree{privateroot:Node;constructor(){this.root=newNode();}modify(left:number,right:number,v:number,l:number=1,r:number=1e9,node:Node|null=null,):void{if(node===null){node=this.root;}if(l>=left&&r<=right){node.v=v===1;node.add=v;return;}this.pushdown(node);constmid=(l+r)>>1;if(left<=mid){this.modify(left,right,v,l,mid,node.left);}if(right>mid){this.modify(left,right,v,mid+1,r,node.right);}this.pushup(node);}query(left:number,right:number,l:number=1,r:number=1e9,node:Node|null=null,):boolean{if(node===null){node=this.root;}if(l>=left&&r<=right){returnnode.v;}this.pushdown(node);constmid=(l+r)>>1;letresult=true;if(left<=mid){result=result&&this.query(left,right,l,mid,node.left);}if(right>mid){result=result&&this.query(left,right,mid+1,r,node.right);}returnresult;}pushup(node:Node):void{node.v=!!(node.left&&node.left.v&&node.right&&node.right.v);}pushdown(node:Node):void{if(node.left===null){node.left=newNode();}if(node.right===null){node.right=newNode();}if(node.add!==0){node.left.add=node.add;node.right.add=node.add;node.left.v=node.add===1;node.right.v=node.add===1;node.add=0;}}}classRangeModule{privatetree:SegmentTree;constructor(){this.tree=newSegmentTree();}addRange(left:number,right:number):void{this.tree.modify(left,right-1,1);}queryRange(left:number,right:number):boolean{returnthis.tree.query(left,right-1);}removeRange(left:number,right:number):void{this.tree.modify(left,right-1,-1);}}/** * Your RangeModule object will be instantiated and called as such: * var obj = new RangeModule() * obj.addRange(left,right) * var param_2 = obj.queryRange(left,right) * obj.removeRange(left,right) */