715. Range Module #
题目 #
A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.
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.queryRange(int left, int right)Returns true if and only if every real number in the interval[left, right)is currently being tracked.removeRange(int left, int right)Stops tracking every real number currently being tracked in the interval[left, right).
Example 1:
addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)
Note:
- A half open interval
[left, right)denotes all real numbersleft <= x < right. 0 < left < right < 10^9in all calls toaddRange, queryRange, removeRange.- The total number of calls to
addRangein a single test case is at most1000. - The total number of calls to
queryRangein a single test case is at most5000. - The total number of calls to
removeRangein a single test case is at most1000.
题目大意 #
Range 模块是跟踪数字范围的模块。你的任务是以一种有效的方式设计和实现以下接口。
- addRange(int left, int right) 添加半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
- queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true。
- removeRange(int left, int right) 停止跟踪区间 [left, right) 中当前正在跟踪的每个实数。
示例：
addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true （区间 [10, 14) 中的每个数都正在被跟踪）
queryRange(13, 15): false （未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
queryRange(16, 17): true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）
提示：
- 半开区间 [left, right) 表示所有满足 left <= x < right 的实数。
- 对 addRange, queryRange, removeRange 的所有调用中 0 < left < right < 10^9。
- 在单个测试用例中，对 addRange 的调用总数不超过 1000 次。
- 在单个测试用例中，对 queryRange 的调用总数不超过 5000 次。
- 在单个测试用例中，对 removeRange 的调用总数不超过 1000 次。
解题思路 #
- 设计一个数据结构，能完成添加区间
addRange，查询区间queryRange，移除区间removeRange三种操作。查询区间的操作需要更加高效一点。 - 这一题可以用线段树来解答，但是时间复杂度不高，最优解是用二叉排序树 BST 来解答。先来看线段树。这一题是更新区间内的值，所以需要用到懒惰更新。添加区间可以把区间内的值都赋值为 1 。由于题目中未预先确定区间范围，选用树的形式实现线段树比数组实现更加节约空间(当然用数组也可以，区间最大是 1000，点至多有 2000 个)。移除区间的时候就是把区间内的值都赋值标记为 0 。
- 类似的题目有：第 699 题，第 218 题，第 732 题。第 715 题是区间更新定值(不是增减)，第 218 题可以用扫描线，第 732 题和第 699 题类似，也是俄罗斯方块的题目，但是第 732 题的俄罗斯方块的方块会“断裂”。
代码 #
package leetcode
// RangeModule define
type RangeModule struct {
Root *SegmentTreeNode
}
// SegmentTreeNode define
type SegmentTreeNode struct {
Start, End int
Tracked bool
Lazy int
Left, Right *SegmentTreeNode
}
// Constructor715 define
func Constructor715() RangeModule {
return RangeModule{&SegmentTreeNode{0, 1e9, false, 0, nil, nil}}
}
// AddRange define
func (rm *RangeModule) AddRange(left int, right int) {
update(rm.Root, left, right-1, true)
}
// QueryRange define
func (rm *RangeModule) QueryRange(left int, right int) bool {
return query(rm.Root, left, right-1)
}
// RemoveRange define
func (rm *RangeModule) RemoveRange(left int, right int) {
update(rm.Root, left, right-1, false)
}
func lazyUpdate(node *SegmentTreeNode) {
if node.Lazy != 0 {
node.Tracked = node.Lazy == 2
}
if node.Start != node.End {
if node.Left == nil || node.Right == nil {
m := node.Start + (node.End-node.Start)/2
node.Left = &SegmentTreeNode{node.Start, m, node.Tracked, 0, nil, nil}
node.Right = &SegmentTreeNode{m + 1, node.End, node.Tracked, 0, nil, nil}
} else if node.Lazy != 0 {
node.Left.Lazy = node.Lazy
node.Right.Lazy = node.Lazy
}
}
node.Lazy = 0
}
func update(node *SegmentTreeNode, start, end int, track bool) {
lazyUpdate(node)
if start > end || node == nil || end < node.Start || node.End < start {
return
}
if start <= node.Start && node.End <= end {
// segment completely covered by the update range
node.Tracked = track
if node.Start != node.End {
if track {
node.Left.Lazy = 2
node.Right.Lazy = 2
} else {
node.Left.Lazy = 1
node.Right.Lazy = 1
}
}
return
}
update(node.Left, start, end, track)
update(node.Right, start, end, track)
node.Tracked = node.Left.Tracked && node.Right.Tracked
}
func query(node *SegmentTreeNode, start, end int) bool {
lazyUpdate(node)
if start > end || node == nil || end < node.Start || node.End < start {
return true
}
if start <= node.Start && node.End <= end {
// segment completely covered by the update range
return node.Tracked
}
return query(node.Left, start, end) && query(node.Right, start, end)
}
// 解法二 BST
// type RangeModule struct {
// Root *BSTNode
// }
// type BSTNode struct {
// Interval []int
// Left, Right *BSTNode
// }
// func Constructor715() RangeModule {
// return RangeModule{}
// }
// func (this *RangeModule) AddRange(left int, right int) {
// interval := []int{left, right - 1}
// this.Root = insert(this.Root, interval)
// }
// func (this *RangeModule) RemoveRange(left int, right int) {
// interval := []int{left, right - 1}
// this.Root = delete(this.Root, interval)
// }
// func (this *RangeModule) QueryRange(left int, right int) bool {
// return query(this.Root, []int{left, right - 1})
// }
// func (this *RangeModule) insert(root *BSTNode, interval []int) *BSTNode {
// if root == nil {
// return &BSTNode{interval, nil, nil}
// }
// if root.Interval[0] <= interval[0] && interval[1] <= root.Interval[1] {
// return root
// }
// if interval[0] < root.Interval[0] {
// root.Left = insert(root.Left, []int{interval[0], min(interval[1], root.Interval[0]-1)})
// }
// if root.Interval[1] < interval[1] {
// root.Right = insert(root.Right, []int{max(interval[0], root.Interval[1]+1), interval[1]})
// }
// return root
// }
// func (this *RangeModule) delete(root *BSTNode, interval []int) *BSTNode {
// if root == nil {
// return nil
// }
// if interval[0] < root.Interval[0] {
// root.Left = delete(root.Left, []int{interval[0], min(interval[1], root.Interval[0]-1)})
// }
// if root.Interval[1] < interval[1] {
// root.Right = delete(root.Right, []int{max(interval[0], root.Interval[1]+1), interval[1]})
// }
// if interval[1] < root.Interval[0] || root.Interval[1] < interval[0] {
// return root
// }
// if interval[0] <= root.Interval[0] && root.Interval[1] <= interval[1] {
// if root.Left == nil {
// return root.Right
// } else if root.Right == nil {
// return root.Left
// } else {
// pred := root.Left
// for pred.Right != nil {
// pred = pred.Right
// }
// root.Interval = pred.Interval
// root.Left = delete(root.Left, pred.Interval)
// return root
// }
// }
// if root.Interval[0] < interval[0] && interval[1] < root.Interval[1] {
// left := &BSTNode{[]int{root.Interval[0], interval[0] - 1}, root.Left, nil}
// right := &BSTNode{[]int{interval[1] + 1, root.Interval[1]}, nil, root.Right}
// left.Right = right
// return left
// }
// if interval[0] <= root.Interval[0] {
// root.Interval[0] = interval[1] + 1
// }
// if root.Interval[1] <= interval[1] {
// root.Interval[1] = interval[0] - 1
// }
// return root
// }
// func (this *RangeModule) query(root *BSTNode, interval []int) bool {
// if root == nil {
// return false
// }
// if interval[1] < root.Interval[0] {
// return query(root.Left, interval)
// }
// if root.Interval[1] < interval[0] {
// return query(root.Right, interval)
// }
// left := true
// if interval[0] < root.Interval[0] {
// left = query(root.Left, []int{interval[0], root.Interval[0] - 1})
// }
// right := true
// if root.Interval[1] < interval[1] {
// right = query(root.Right, []int{root.Interval[1] + 1, interval[1]})
// }
// return left && right
// }
/**
* 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);
*/