715. Range Module #

Problem #

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 numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

Main Idea of the Problem #

Range module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient way.

addRange(int left, int right) adds the half-open interval [left, right), tracking every real number in that interval. When adding an interval that partially overlaps the currently tracked numbers, any numbers in the interval [left, right) that are not yet tracked should be added to that interval.
queryRange(int left, int right) returns true only when 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:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true （every number in the interval [10, 14) is being tracked）
queryRange(13, 15): false （numbers such as 14, 14.03, 14.17 in the interval [13, 15) are not tracked）
queryRange(16, 17): true （although a delete operation was performed, the number 16 in the interval [16, 17) will still be tracked）

Hints:

The half-open interval [left, right) represents all real numbers satisfying left <= x < right.
In all calls to addRange, queryRange, removeRange, 0 < left < right < 10^9.
In a single test case, the total number of calls to addRange does not exceed 1000.
In a single test case, the total number of calls to queryRange does not exceed 5000.
In a single test case, the total number of calls to removeRange does not exceed 1000.

Solution Ideas #

Design a data structure that can perform the three operations of adding an interval addRange, querying an interval queryRange, and removing an interval removeRange. The query interval operation needs to be a bit more efficient.
This problem can be solved with a segment tree, but the time complexity is not low; the optimal solution is to use a binary search tree BST. First, look at the segment tree. This problem updates the values within an interval, so lazy updates are needed. Adding an interval can assign all values within the interval to 1. Since the interval range is not predetermined in the problem, implementing the segment tree in tree form saves more space than an array implementation (of course, an array can also be used; the maximum number of intervals is 1000, and there are at most 2000 points). When removing an interval, assign all values within the interval and mark them as 0.
Similar problems include: Problem 699, Problem 218, and Problem 732. Problem 715 is interval update to a fixed value (not increment or decrement), Problem 218 can be solved with a sweep line, and Problem 732 is similar to Problem 699; it is also a Tetris problem, but the blocks in Problem 732’s Tetris can “break apart”.

Code #


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)
}

// Solution Two 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);
 */