[Google] LeetCode 715 Range Module 线段树
2022/8/30 23:26:21
本文主要是介绍[Google] LeetCode 715 Range Module 线段树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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)
Returnstrue
if every real number in the interval[left, right)
is currently being tracked, andfalse
otherwise.void removeRange(int left, int right)
Stops tracking every real number currently being tracked in the half-open interval[left, right)
.
Solution
我们需要进行区间修改以及区间查询,这里使用 线段树 来解决。
点击查看代码
class RangeModule { private: struct node{ bool val = false; bool lazy = false; node* lt = NULL; node* rt = NULL; }; int LIMIT = 1e9+1; node* root; queue<node*> nodeq; node* getNode(){ if(nodeq.empty())return new node(); else{ node* nd = nodeq.front(); nodeq.pop(); if(nd->lt)nodeq.push(nd->lt); if(nd->rt)nodeq.push(nd->rt); nd->val = false; nd->lazy = false; nd->lt = NULL; nd->rt=NULL; return nd; } } bool query(node* nd, int s, int t, int l,int r){ if(!nd->lt) nd->lt = getNode(); if(!nd->rt) nd->rt = getNode(); if(nd->lazy){ nd->val|=nd->lazy; if(s!=t){ nd->lt->lazy|=nd->lazy; nd->rt->lazy|=nd->lazy; } nd->lazy=false; } if(t<l || s>r) return true; if(nd->val) return nd->val; if(l<=s && t<=r) return nd->val; int mid = s + (t-s)/2; return query(nd->lt, s, mid,l,r) && query(nd->rt, mid+1, t, l,r); } void upd(node* nd, int s, int t, int l, int r){ if(!nd->lt) nd->lt = getNode(); if(!nd->rt) nd->rt = getNode(); if(nd->lazy) { nd->val|=nd->lazy; if(s!=t){ nd->lt->lazy |= nd->lazy; nd->rt->lazy |= nd->lazy; } nd->lazy = false; } if(t<l || s>r) return; if(nd->val) return; if(l<=s && t<=r){ nd->val=true; if(s!=t){ nd->lt->lazy=true; nd->rt->lazy=true; } return; } int mid=s+(t-s)/2; upd(nd->lt, s, mid, l,r); upd(nd->rt, mid+1, t, l, r); nd->val = nd->lt->val && nd->rt->val; } void rmv(node* nd, int s,int t, int l,int r){ if(t<l || s>r) return; if(l<=s && t<= r){ nd->val = false; nd->lazy = false; if(nd->lt) nodeq.push(nd->lt); if(nd->rt) nodeq.push(nd->rt); nd->lt = NULL; nd->rt = NULL; return; } if(!nd->lt) nd->lt = getNode(); if(!nd->rt) nd->rt = getNode(); if(nd->lazy){ nd->val|=nd->lazy; if(s!=t){ nd->lt->lazy|=nd->lazy; nd->rt->lazy|=nd->lazy; } nd->lazy = false; } int mid = s+(t-s)/2; rmv(nd->lt, s, mid, l,r); rmv(nd->rt, mid+1, t, l, r); nd->val = nd->lt->val && nd->rt->val; } public: RangeModule() { root = new node(); } void addRange(int left, int right) { upd(root, 0, LIMIT, left, right-1); } bool queryRange(int left, int right) { return query(root, 0, LIMIT, left, right-1); } void removeRange(int left, int right) { rmv(root, 0, LIMIT, left, right-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); */
这篇关于[Google] LeetCode 715 Range Module 线段树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-20go-zero 框架的 RPC 服务 启动start和停止 底层是怎么实现的?-icode9专业技术文章分享
- 2024-12-19Go-Zero 框架的 RPC 服务启动和停止的基本机制和过程是怎么实现的?-icode9专业技术文章分享
- 2024-12-18怎么在golang中使用gRPC测试mock数据?-icode9专业技术文章分享
- 2024-12-15掌握PageRank算法核心!你离Google优化高手只差一步!
- 2024-12-15GORM 中的标签 gorm:"index"是什么?-icode9专业技术文章分享
- 2024-12-11怎么在 Go 语言中获取 Open vSwitch (OVS) 的桥接信息(Bridge)?-icode9专业技术文章分享
- 2024-12-11怎么用Go 语言的库来与 Open vSwitch 进行交互?-icode9专业技术文章分享
- 2024-12-11怎么在 go-zero 项目中发送阿里云短信?-icode9专业技术文章分享
- 2024-12-11怎么使用阿里云 Go SDK (alibaba-cloud-sdk-go) 发送短信?-icode9专业技术文章分享
- 2024-12-10搭建个人博客网站之一、使用hugo创建个人博客网站