715. Range 模块
Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。
半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。
实现 RangeModule 类:
RangeModule() 初始化数据结构的对象。void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。
示例 1：
输入 ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]] 输出 [null, null, null, true, false, true] 解释 RangeModule rangeModule = new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪） rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字） rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
提示：
1 <= left < right <= 109addRange 、 queryRange 和 removeRange 的调用总数不超过 104 次原站题解
cpp 解法, 执行用时: 188 ms, 内存消耗: 69 MB, 提交时间: 2023-11-12 00:27:48
class RangeModule {
public:
RangeModule() {}
void addRange(int left, int right) {
auto it = intervals.upper_bound(left);
if (it != intervals.begin()) {
auto start = prev(it);
if (start->second >= right) {
return;
}
if (start->second >= left) {
left = start->first;
intervals.erase(start);
}
}
while (it != intervals.end() && it->first <= right) {
right = max(right, it->second);
it = intervals.erase(it);
}
intervals[left] = right;
}
bool queryRange(int left, int right) {
auto it = intervals.upper_bound(left);
if (it == intervals.begin()) {
return false;
}
it = prev(it);
return right <= it->second;
}
void removeRange(int left, int right) {
auto it = intervals.upper_bound(left);
if (it != intervals.begin()) {
auto start = prev(it);
if (start->second >= right) {
int ri = start->second;
if (start->first == left) {
intervals.erase(start);
}
else {
start->second = left;
}
if (right != ri) {
intervals[right] = ri;
}
return;
}
else if (start->second > left) {
if (start->first == left) {
intervals.erase(start);
}
else {
start->second = left;
}
}
}
while (it != intervals.end() && it->first < right) {
if (it->second <= right) {
it = intervals.erase(it);
}
else {
intervals[right] = it->second;
intervals.erase(it);
break;
}
}
}
private:
map<int, int> intervals;
};
/**
* 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);
*/
golang 解法, 执行用时: 532 ms, 内存消耗: 23.9 MB, 提交时间: 2022-12-04 17:49:12
const MAX_RANGE = 1000000009
type RangeModule struct {
Root *SegmentNode
}
func Constructor() RangeModule {
return RangeModule{&SegmentNode{nil, nil, false, false}}
}
func (this *RangeModule) AddRange(left int, right int) {
this.Root.update(1, MAX_RANGE, left, right - 1, true)
}
func (this *RangeModule) QueryRange(left int, right int) bool {
return this.Root.query(1, MAX_RANGE, left, right - 1)
}
func (this *RangeModule) RemoveRange(left int, right int) {
this.Root.update(1, MAX_RANGE, left, right - 1, false)
}
/**
* 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);
*/
type SegmentNode struct {
Ls, Rs *SegmentNode
Val, Add bool
}
func (node *SegmentNode) update(lc int, rc int, l int, r int, v bool) {
if l <= lc && rc <= r {
node.Val, node.Add = v, true
return
}
node.pushdown()
mid := (lc + rc) >> 1
if l <= mid {
node.Ls.update(lc, mid, l, r, v)
}
if r > mid {
node.Rs.update(mid + 1, rc, l, r, v)
}
node.pushup()
}
func (node *SegmentNode) query(lc int, rc int, l int, r int) bool {
if l <= lc && rc <= r {
return node.Val
}
node.pushdown()
mid, ans := (lc + rc) >> 1, true
if l <= mid {
ans = ans && node.Ls.query(lc, mid, l, r)
}
if r > mid {
ans = ans && node.Rs.query(mid + 1, rc, l, r)
}
return ans
}
func (node *SegmentNode) pushup() {
node.Val = node.Ls.Val && node.Rs.Val
}
func (node *SegmentNode) pushdown() {
if node.Ls == nil {
node.Ls = &SegmentNode{nil, nil, false, false}
}
if node.Rs == nil {
node.Rs = &SegmentNode{nil, nil, false, false}
}
if !node.Add {
return
}
node.Ls.Val, node.Ls.Add, node.Rs.Val, node.Rs.Add = node.Val, true, node.Val, true
node.Add = false
}
python3 解法, 执行用时: 8392 ms, 内存消耗: 67.8 MB, 提交时间: 2022-12-04 17:48:33
MAX_RANGE = int(1e9 + 7)
class Node:
def __init__(self) -> None:
self.ls = self.rs = None
self.val = self.add = False
class SegmentTree:
def __init__(self):
self.root = Node()
@staticmethod
def update(node: Node, lc: int, rc: int, l: int, r: int, v: bool) -> None:
if l <= lc and rc <= r:
node.val = v
# 注意产生变化懒标记就为True，因为更新有删除
node.add = True
return
SegmentTree.pushdown(node)
mid = (lc + rc) >> 1
if l <= mid:
SegmentTree.update(node.ls, lc, mid, l, r, v)
if r > mid:
SegmentTree.update(node.rs, mid + 1, rc, l, r, v)
SegmentTree.pushup(node)
@staticmethod
def query(node: Node, lc: int, rc: int, l: int, r: int) -> bool:
if l <= lc and rc <= r:
return node.val
# 先确保所有关联的懒标记下沉下去
SegmentTree.pushdown(node)
mid, ans = (lc + rc) >> 1, True
if l <= mid:
ans = ans and SegmentTree.query(node.ls, lc, mid, l, r)
if r > mid:
# 同样为不同题目中的更新方式
ans = ans and SegmentTree.query(node.rs, mid + 1, rc, l, r)
return ans
@staticmethod
def pushdown(node: Node) -> None:
# 懒标记, 在需要的时候才开拓节点和赋值
if node.ls is None:
node.ls = Node()
if node.rs is None:
node.rs = Node()
if not node.add:
return
node.ls.val, node.rs.val = node.val, node.val
# 注意产生变化懒标记就为True，因为更新有删除
node.ls.add, node.rs.add = True, True
node.add = False
@staticmethod
def pushup(node: Node) -> None:
# 动态更新方式：此处为两者都true
node.val = node.ls.val and node.rs.val
class RangeModule:
def __init__(self):
self.st = SegmentTree()
def addRange(self, left: int, right: int) -> None:
SegmentTree.update(self.st.root, 1, MAX_RANGE, left, right - 1, True)
def queryRange(self, left: int, right: int) -> bool:
return SegmentTree.query(self.st.root, 1, MAX_RANGE, left, right - 1)
def removeRange(self, left: int, right: int) -> None:
SegmentTree.update(self.st.root, 1, MAX_RANGE, left, right - 1, False)
# 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)
java 解法, 执行用时: 43 ms, 内存消耗: 49.2 MB, 提交时间: 2022-12-04 17:46:33
class RangeModule {
TreeMap<Integer, Integer> intervals;
public RangeModule() {
intervals = new TreeMap<Integer, Integer>();
}
public void addRange(int left, int right) {
Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
if (entry != intervals.firstEntry()) {
Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
if (start != null && start.getValue() >= right) {
return;
}
if (start != null && start.getValue() >= left) {
left = start.getKey();
intervals.remove(start.getKey());
}
}
while (entry != null && entry.getKey() <= right) {
right = Math.max(right, entry.getValue());
intervals.remove(entry.getKey());
entry = intervals.higherEntry(entry.getKey());
}
intervals.put(left, right);
}
public boolean queryRange(int left, int right) {
Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
if (entry == intervals.firstEntry()) {
return false;
}
entry = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
return entry != null && right <= entry.getValue();
}
public void removeRange(int left, int right) {
Map.Entry<Integer, Integer> entry = intervals.higherEntry(left);
if (entry != intervals.firstEntry()) {
Map.Entry<Integer, Integer> start = entry != null ? intervals.lowerEntry(entry.getKey()) : intervals.lastEntry();
if (start != null && start.getValue() >= right) {
int ri = start.getValue();
if (start.getKey() == left) {
intervals.remove(start.getKey());
} else {
intervals.put(start.getKey(), left);
}
if (right != ri) {
intervals.put(right, ri);
}
return;
} else if (start != null && start.getValue() > left) {
if (start.getKey() == left) {
intervals.remove(start.getKey());
} else {
intervals.put(start.getKey(), left);
}
}
}
while (entry != null && entry.getKey() < right) {
if (entry.getValue() <= right) {
intervals.remove(entry.getKey());
entry = intervals.higherEntry(entry.getKey());
} else {
intervals.put(right, entry.getValue());
intervals.remove(entry.getKey());
break;
}
}
}
}
/**
* 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);
*/
golang 解法, 执行用时: 180 ms, 内存消耗: 8.5 MB, 提交时间: 2022-12-04 17:46:08
type RangeModule struct {
*redblacktree.Tree
}
func Constructor() RangeModule {
return RangeModule{redblacktree.NewWithIntComparator()}
}
func (t RangeModule) AddRange(left, right int) {
if node, ok := t.Floor(left); ok {
r := node.Value.(int)
if r >= right {
return
}
if r >= left {
left = node.Key.(int)
t.Remove(left)
}
}
for node, ok := t.Ceiling(left); ok && node.Key.(int) <= right; node, ok = t.Ceiling(left) {
right = max(right, node.Value.(int))
t.Remove(node.Key)
}
t.Put(left, right)
}
func (t RangeModule) QueryRange(left, right int) bool {
node, ok := t.Floor(left)
return ok && node.Value.(int) >= right
}
func (t RangeModule) RemoveRange(left, right int) {
if node, ok := t.Floor(left); ok {
l, r := node.Key.(int), node.Value.(int)
if r >= right {
if l == left {
t.Remove(l)
} else {
node.Value = left
}
if right != r {
t.Put(right, r)
}
return
}
if r > left {
if l == left {
t.Remove(l)
} else {
node.Value = left
}
}
}
for node, ok := t.Ceiling(left); ok && node.Key.(int) < right; node, ok = t.Ceiling(left) {
r := node.Value.(int)
t.Remove(node.Key)
if r > right {
t.Put(right, r)
break
}
}
}
func max(a, b int) int {
if b > a {
return b
}
return a
}
/**
* 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);
*/
python3 解法, 执行用时: 444 ms, 内存消耗: 20.3 MB, 提交时间: 2022-12-04 17:45:45
from sortedcontainers import SortedDict
class RangeModule:
def __init__(self):
self.intervals = SortedDict()
def addRange(self, left: int, right: int) -> None:
itvs_ = self.intervals
x = itvs_.bisect_right(left)
if x != 0:
start = x - 1
if itvs_.values()[start] >= right:
return
if itvs_.values()[start] >= left:
left = itvs_.keys()[start]
itvs_.popitem(start)
x -= 1
while x < len(itvs_) and itvs_.keys()[x] <= right:
right = max(right, itvs_.values()[x])
itvs_.popitem(x)
itvs_[left] = right
def queryRange(self, left: int, right: int) -> bool:
itvs_ = self.intervals
x = itvs_.bisect_right(left)
if x == 0:
return False
return right <= itvs_.values()[x - 1]
def removeRange(self, left: int, right: int) -> None:
itvs_ = self.intervals
x = itvs_.bisect_right(left)
if x != 0:
start = x - 1
if (ri := itvs_.values()[start]) >= right:
if (li := itvs_.keys()[start]) == left:
itvs_.popitem(start)
else:
itvs_[li] = left
if right != ri:
itvs_[right] = ri
return
elif ri > left:
if (li := itvs_.keys()[start]) == left:
itvs_.popitem(start)
x -= 1
else:
itvs_[itvs_.keys()[start]] = left
while x < len(itvs_) and itvs_.keys()[x] < right:
if itvs_.values()[x] <= right:
itvs_.popitem(x)
else:
itvs_[right] = itvs_.values()[x]
itvs_.popitem(x)
break
# 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)