Description#
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class Node:
__slots__ = ['left', 'right', 'add', 'v']
def __init__(self):
self.left = None
self.right = None
self.add = 0
self.v = False
class SegmentTree:
__slots__ = ['root']
def __init__(self):
self.root = Node()
def modify(self, left, right, v, l=1, r=int(1e9), node=None):
if node is None:
node = self.root
if l >= left and r <= right:
if v == 1:
node.add = 1
node.v = True
else:
node.add = -1
node.v = False
return
self.pushdown(node)
mid = (l + r) >> 1
if left <= mid:
self.modify(left, right, v, l, mid, node.left)
if right > mid:
self.modify(left, right, v, mid + 1, r, node.right)
self.pushup(node)
def query(self, left, right, l=1, r=int(1e9), node=None):
if node is None:
node = self.root
if l >= left and r <= right:
return node.v
self.pushdown(node)
mid = (l + r) >> 1
v = True
if left <= mid:
v = v and self.query(left, right, l, mid, node.left)
if right > mid:
v = v and self.query(left, right, mid + 1, r, node.right)
return v
def pushup(self, node):
node.v = bool(node.left and node.left.v and node.right and node.right.v)
def pushdown(self, node):
if node.left is None:
node.left = Node()
if node.right is None:
node.right = Node()
if node.add:
node.left.add = node.right.add = node.add
node.left.v = node.add == 1
node.right.v = node.add == 1
node.add = 0
class RangeModule:
def __init__(self):
self.tree = SegmentTree()
def addRange(self, left: int, right: int) -> None:
self.tree.modify(left, right - 1, 1)
def queryRange(self, left: int, right: int) -> bool:
return self.tree.query(left, right - 1)
def removeRange(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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| class Node {
Node left;
Node right;
int add;
boolean v;
}
class SegmentTree {
private Node root = new Node();
public SegmentTree() {
}
public void modify(int left, int right, int v) {
modify(left, right, v, 1, (int) 1e9, root);
}
public void modify(int left, int right, int v, int l, int r, Node node) {
if (l >= left && r <= right) {
node.v = v == 1;
node.add = v;
return;
}
pushdown(node);
int mid = (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);
}
public boolean query(int left, int right) {
return query(left, right, 1, (int) 1e9, root);
}
public boolean query(int left, int right, int l, int r, Node node) {
if (l >= left && r <= right) {
return node.v;
}
pushdown(node);
int mid = (l + r) >> 1;
boolean v = 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);
}
return v;
}
public void pushup(Node node) {
node.v = node.left != null && node.left.v && node.right != null && node.right.v;
}
public void pushdown(Node node) {
if (node.left == null) {
node.left = new Node();
}
if (node.right == null) {
node.right = new Node();
}
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;
}
}
}
class RangeModule {
private SegmentTree tree = new SegmentTree();
public RangeModule() {
}
public void addRange(int left, int right) {
tree.modify(left, right - 1, 1);
}
public boolean queryRange(int left, int right) {
return tree.query(left, right - 1);
}
public void removeRange(int left, int right) {
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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| template <class T>
class CachedObj {
public:
void* operator new(size_t s) {
if (!head) {
T* a = new T[SIZE];
for (size_t i = 0; i < SIZE; ++i)
add(a + i);
}
T* p = head;
head = head->CachedObj<T>::next;
return p;
}
void operator delete(void* p, size_t) {
if (p) add(static_cast<T*>(p));
}
virtual ~CachedObj() {}
protected:
T* next;
private:
static T* head;
static const size_t SIZE;
static void add(T* p) {
p->CachedObj<T>::next = head;
head = p;
}
};
template <class T>
T* CachedObj<T>::head = 0;
template <class T>
const size_t CachedObj<T>::SIZE = 10000;
class Node : public CachedObj<Node> {
public:
Node* left;
Node* right;
int add;
bool v;
};
class SegmentTree {
private:
Node* root;
public:
SegmentTree() {
root = new Node();
}
void modify(int left, int right, int v) {
modify(left, right, v, 1, 1e9, root);
}
void modify(int left, int right, int v, int l, int r, Node* node) {
if (l >= left && r <= right) {
node->v = v == 1;
node->add = v;
return;
}
pushdown(node);
int mid = (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);
}
bool query(int left, int right) {
return query(left, right, 1, 1e9, root);
}
bool query(int left, int right, int l, int r, Node* node) {
if (l >= left && r <= right) return node->v;
pushdown(node);
int mid = (l + r) >> 1;
bool v = 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);
return v;
}
void pushup(Node* node) {
node->v = node->left && node->left->v && node->right && node->right->v;
}
void pushdown(Node* node) {
if (!node->left) node->left = new Node();
if (!node->right) node->right = new Node();
if (node->add) {
node->left->add = node->right->add = node->add;
node->left->v = node->right->v = node->add == 1;
node->add = 0;
}
}
};
class RangeModule {
public:
SegmentTree* tree;
RangeModule() {
tree = new SegmentTree();
}
void addRange(int left, int right) {
tree->modify(left, right - 1, 1);
}
bool queryRange(int left, int right) {
return tree->query(left, right - 1);
}
void removeRange(int left, int right) {
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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
| const N int = 1e9
type node struct {
lch *node
rch *node
added bool
lazy int
}
type segmentTree struct {
root *node
}
func newSegmentTree() *segmentTree {
return &segmentTree{
root: new(node),
}
}
func (t *segmentTree) update(n *node, l, r, i, j, x int) {
if l >= i && r <= j {
n.added = x == 1
n.lazy = x
return
}
t.pushdown(n)
m := int(uint(l+r) >> 1)
if i <= m {
t.update(n.lch, l, m, i, j, x)
}
if j > m {
t.update(n.rch, m+1, r, i, j, x)
}
t.pushup(n)
}
func (t *segmentTree) query(n *node, l, r, i, j int) bool {
if l >= i && r <= j {
return n.added
}
t.pushdown(n)
v := true
m := int(uint(l+r) >> 1)
if i <= m {
v = v && t.query(n.lch, l, m, i, j)
}
if j > m {
v = v && t.query(n.rch, m+1, r, i, j)
}
return v
}
func (t *segmentTree) pushup(n *node) {
n.added = n.lch.added && n.rch.added
}
func (t *segmentTree) pushdown(n *node) {
if n.lch == nil {
n.lch = new(node)
}
if n.rch == nil {
n.rch = new(node)
}
if n.lazy != 0 {
n.lch.added = n.lazy == 1
n.rch.added = n.lazy == 1
n.lch.lazy = n.lazy
n.rch.lazy = n.lazy
n.lazy = 0
}
}
type RangeModule struct {
t *segmentTree
}
func Constructor() RangeModule {
return RangeModule{
t: newSegmentTree(),
}
}
func (this *RangeModule) AddRange(left int, right int) {
this.t.update(this.t.root, 1, N, left, right-1, 1)
}
func (this *RangeModule) QueryRange(left int, right int) bool {
return this.t.query(this.t.root, 1, N, left, right-1)
}
func (this *RangeModule) RemoveRange(left int, right int) {
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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
| class Node {
left: Node | null;
right: Node | null;
add: number;
v: boolean;
constructor() {
this.left = null;
this.right = null;
this.add = 0;
this.v = false;
}
}
class SegmentTree {
private root: Node;
constructor() {
this.root = new Node();
}
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);
const mid = (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) {
return node.v;
}
this.pushdown(node);
const mid = (l + r) >> 1;
let result = 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);
}
return result;
}
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 = new Node();
}
if (node.right === null) {
node.right = new Node();
}
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;
}
}
}
class RangeModule {
private tree: SegmentTree;
constructor() {
this.tree = new SegmentTree();
}
addRange(left: number, right: number): void {
this.tree.modify(left, right - 1, 1);
}
queryRange(left: number, right: number): boolean {
return this.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)
*/
|
