715. Range Module

HardDesignSegment TreeOrdered Set

Problem Description

A Range Module is asked to manage and track ranges of numbers within its data structure, specifically defined as half-open intervals [left, right). A half-open interval includes the left boundary and excludes the right boundary, which could represent all real numbers x where left <= x < right. The Range Module will support adding new ranges, querying if a given range is fully tracked, and removing existing ranges.

We have to implement a RangeModule class with the following functions:

RangeModule() - a constructor method to initialize the range tracking data structure.
addRange(int left, int right) - this method should add a half-open interval [left, right), tracking all the real numbers within that interval. If the new interval overlaps with any currently tracked numbers, only those not already tracked should be added.
queryRange(int left, int right) - this method should return true if every real number in the interval [left, right) is currently tracked. Otherwise, it returns false.
removeRange(int left, int right) - this method should stop tracking any real number in the half-open interval [left, right) that is currently being tracked.

The best way to manage these ranges effectively, given that the intervals could be large, is to use an interval tree or segment tree data structure.

Intuition

To solve this problem efficiently, we need a data structure that can handle dynamic range updates and queries. The segment tree is an ideal choice here due to its ability to maintain information about intervals and support operations and queries in logarithmic time complexity.

A segment tree is a tree-like data structure that stores aggregates for a range of array indices. In this context, we're interested in tracking if a range is fully added, not added, or partially added. To accommodate these conditions and to facilitate lazy propagation of updates (deferred tree updates until needed to save time), we extend the segment tree with flags that indicate the addition or removal of ranges.

Here's the breakdown for the intuition behind the proposed solution:

Segment Tree Initialization: Construct a Segment Tree with a sufficient range to cover the possible inputs. We start with a root node representing the entire range.
Add and Remove Ranges: When adding or removing a range, the tree nodes corresponding to that interval are updated. If a node's interval is entirely covered by the range, its flag is updated, and so is the v property indicating whether the range is fully added or removed.
Lazy Propagation: To conserve operations, we propagate changes only when necessary (when we need to go deeper into an interval that was previously updated but not propagated). We update child nodes only when a query or further update for a sub-interval within the affected range occurs.
Querying Ranges: To check whether an interval is fully tracked, we inspect the tree nodes associated with that interval. If all parts demonstrate that they are fully tracked, we return true; otherwise, we return false.

The Segment Tree used in the code is slightly specialized for this problem. Instead of maintaining a count or sum over an interval, each node in the Segment Tree stores whether the interval is fully included in the tracking (node.v) and a propagation flag (node.add) that indicates whether an add or remove operation should be propagated to the node's children.

This approach efficiently supports the three operations required by the Range Module: adding, querying, and removing ranges. The time complexity for each operation is O(log n), making it appropriate for problems with large ranges of numbers and many operations.

Learn more about Segment Tree patterns.

Solution Approach

The solution uses a Segment Tree to manage the intervals, which inherently uses a divide and conquer strategy. A Segment Tree is a binary tree data structure where each node represents an interval. For this problem, we use the Segment Tree to track whether intervals are fully included (node.v) or not, and we make sure to propagate any changes if necessary through the use of a lazy propagation technique (node.add).

Here's a step-by-step breakdown of the key elements of the Segment Tree as implemented in this solution:

Node Structure: Each Node of the Segment Tree has two child nodes (left and right), the add property, and a boolean value v. The add property indicates the pending operation that should be applied to this node's range (1 for adding, -1 for removing), and the v property shows whether the current interval is completely added.
Segment Tree Initialization: The SegmentTree class has a root node that initially represents the entire range [1, 1e9).
The modify Function: This function recursively updates nodes in the Segment Tree to reflect added or removed intervals. It receives the interval (left, right) and a value v indicating whether to add (1) or remove (-1). The function:
- Updates the current node if its interval is completely within the range.
- Calls pushdown to propagate any pending updates to the children.
- Recursively calls itself to update the children nodes if they overlap with the range.
- Calls pushup to update the parent node based on the update results from the children.
Lazy Propagation (pushdown and pushup Functions): The lazy propagation is handled by two functions:
- pushdown: It takes a node and propagates the pending add operation, if any, to the children nodes, ensuring that further recursive calls will operate on updated intervals.
- pushup: It updates the node.v based on the values of the children, setting it to True only if both children intervals are fully tracked.
The query Function: Checks if the interval is completely tracked within the range. It recursively checks nodes overlapping with the given interval and returns True only if all parts of the interval are fully tracked.
RangeModule Class: This class utilizes the SegmentTree and exposes the addRange, queryRange, and removeRange methods.
- addRange(left, right): It calls the modify function of the tree to add the interval [left, right - 1) since the interval is half-open.
- queryRange(left, right): It calls the query function of the tree to check if the interval [left, right - 1) is fully tracked.
- removeRange(left, right): Similar to addRange, it calls the modify function but with the intention to remove the interval by using -1 as the value.

This approach is efficient and scalable due to the nature of Segment Trees in handling a large number of interval-based operations with time complexity in O(log n), which is due to the tree's balanced structure.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate how the RangeModule works with a simple example. Consider a Range Module that initially tracks no numbers. We'll perform a sequence of operations and see how the internal data structure (a Segment Tree in this case) deals with these operations.

Example Scenario:

addRange(5, 8): Adds the interval [5, 8) to the tracking. Internally, the Segment Tree will update the nodes corresponding to this range, setting the node.v to True for this interval and using lazy propagation if necessary.
queryRange(3, 7): Queries whether the interval [3, 7) is entirely tracked. The tree checks the nodes that cover this range. Since the interval [5, 7) within the query is tracked but [3, 5) is not, the query function returns False.
addRange(7, 10): Adds the interval [7, 10) to the tracking. The tree updates nodes from 7 to 10. After this addition, the interval [5, 10) is now fully tracked.
queryRange(5, 10): Now, when querying this interval, the query function will check the nodes covering [5, 10). Since both [5, 8) and [7, 10) are tracked (with overlap), the query returns True, confirming the entire range is tracked.
removeRange(5, 6): Stops tracking the interval [5, 6). The tree updates the relevant nodes, setting node.v to False for this range and using lazy propagation to defer updates to its child nodes until needed.
queryRange(5, 10): After the removal, a query for [5, 10) would once again return False because not all numbers in this range are tracked. Specifically, the interval [5, 6) is not tracked anymore.

The Segment Tree efficiently handles these updates and queries, allowing for scalable range management without having to traverse the entire range every time we perform an operation. This is why the structure is particularly well-suited for the Range Module functionality, which may involve a large number of operations on potentially large ranges. Each operation - adding, querying, and removing - works with a time complexity of O(log n), where n is the number of nodes in the tree, which corresponds to the interval lengths being managed.

Solution Implementation

1class Node:
2    def __init__(self):
3        self.left = None  # Pointer to the left child Node
4        self.right = None  # Pointer to the right child Node
5        self.is_covered = False  # Flag to check if the interval is fully covered
6        self.lazy = 0  # Lazy propagation mark to delay updates
7
8class SegmentTree:
9    def __init__(self):
10        self.root = Node()  # Initialize the tree with a root Node
11
12    def modify(self, start, end, value, left=1, right=int(1e9), node=None):
13        """Update the segments covered by the [start, end] range with `value`."""
14        if node is None:
15            node = self.root
16        if left >= start and right <= end:
17            node.lazy = value
18            node.is_covered = (value == 1)
19            return
20        self.pushdown(node)  # Apply any pending updates
21        mid = (left + right) >> 1  # Find the mid to partition the tree
22        if start <= mid:
23            self.modify(start, end, value, left, mid, node.left or Node())
24        if end > mid:
25            self.modify(start, end, value, mid + 1, right, node.right or Node())
26        self.pushup(node)  # Update the parent node
27
28    def query(self, start, end, left=1, right=int(1e9), node=None):
29        """Query the segments covered by the [start, end] range."""
30        if node is None:
31            node = self.root
32        if left >= start and right <= end:
33            return node.is_covered
34        self.pushdown(node)
35        mid = (left + right) >> 1
36        covered = True
37        if start <= mid:
38            covered = covered and (node.left and self.query(start, end, left, mid, node.left))
39        if end > mid:
40            covered = covered and (node.right and self.query(start, end, mid + 1, right, node.right))
41        return covered
42
43    def pushup(self, node):
44        """Update the node based on its children's values."""
45        node.is_covered = (node.left and node.left.is_covered and node.right and node.right.is_covered)
46
47    def pushdown(self, node):
48        """Propagate updates to child nodes if there is a lazy value."""
49        if not (node.left or node.right):
50            node.left = Node()
51            node.right = Node()
52        if node.lazy:
53            for child in [node.left, node.right]:
54                child.lazy = node.lazy
55                child.is_covered = (node.lazy == 1)
56            node.lazy = 0
57
58class RangeModule:
59    def __init__(self):
60        self.tree = SegmentTree()
61
62    def addRange(self, left: int, right: int) -> None:
63        """Add a range [left, right) to the module."""
64        self.tree.modify(left, right - 1, 1)
65
66    def queryRange(self, left: int, right: int) -> bool:
67        """Query if the range [left, right) is fully covered."""
68        return self.tree.query(left, right - 1)
69
70    def removeRange(self, left: int, right: int) -> None:
71        """Remove the range [left, right) from the module."""
72        self.tree.modify(left, right - 1, -1)
73
74# The RangeModule object will be instantiated and called as such:
75# obj = RangeModule()
76# obj.addRange(left,right)
77# param_2 = obj.queryRange(left,right)
78# obj.removeRange(left,right)
79

1// Node class to represent each segment in the Segment Tree
2class Node {
3    Node left;
4    Node right;
5    int valueToAdd;
6    boolean isCovered;
7}
8
9// SegmentTree class encapsulating the tree operations
10class SegmentTree {
11    private Node root = new Node();
12
13    // Constructor is not necessary, Java provides a default one
14
15    // Update the segment tree, marking ranges
16    public void modify(int left, int right, int value) {
17        modify(left, right, value, 1, (int) 1e9, root);
18    }
19
20    // Helper function to modify nodes in the given range [left, right] recursively
21    private void modify(int left, int right, int value, int start, int end, Node node) {
22        if (start >= left && end <= right) {
23            node.isCovered = value == 1;
24            node.valueToAdd = value;
25            return;
26        }
27        pushdown(node);
28      
29        int mid = (start + end) >> 1; // Equivalent to dividing by 2
30        if (left <= mid) {
31            modify(left, right, value, start, mid, node.left);
32        }
33        if (right > mid) {
34            modify(left, right, value, mid + 1, end, node.right);
35        }
36        pushup(node);
37    }
38
39    // Query the segment tree to check coverage of range [left, right]
40    public boolean query(int left, int right) {
41        return query(left, right, 1, (int) 1e9, root);
42    }
43
44    // Helper function to query the tree recursively
45    private boolean query(int left, int right, int start, int end, Node node) {
46        if (node == null) {
47            return false;
48        }
49        if (start >= left && end <= right) {
50            return node.isCovered;
51        }
52
53        pushdown(node);
54
55        int mid = (start + end) >> 1;
56        boolean result = true;
57        if (left <= mid) {
58            result = result && query(left, right, start, mid, node.left);
59        }
60        if (right > mid) {
61            result = result && query(left, right, mid + 1, end, node.right);
62        }
63        return result;
64    }
65
66    // Function to update node coverage based on child nodes
67    private void pushup(Node node) {
68        if (node.left != null && node.right != null) {
69            node.isCovered = node.left.isCovered && node.right.isCovered;
70        }
71    }
72
73    // Function to propagate changes to child nodes
74    private void pushdown(Node node) {
75        if (node.left == null) node.left = new Node();
76        if (node.right == null) node.right = new Node();
77
78        if (node.valueToAdd != 0) {
79            // Propagate valueToAdd down to children and reset it for the current node
80            node.left.valueToAdd = node.valueToAdd;
81            node.right.valueToAdd = node.valueToAdd;
82            node.left.isCovered = node.valueToAdd == 1;
83            node.right.isCovered = node.valueToAdd == 1;
84            node.valueToAdd = 0;
85        }
86    }
87}
88
89// RangeModule class to handle range adding, querying, and removing
90class RangeModule {
91    private SegmentTree tree = new SegmentTree();
92
93    // Adds a range to the module
94    public void addRange(int left, int right) {
95        tree.modify(left, right - 1, 1);
96    }
97
98    // Queries if the range is fully covered
99    public boolean queryRange(int left, int right) {
100        return tree.query(left, right - 1);
101    }
102
103    // Removes a range from the module
104    public void removeRange(int left, int right) {
105        tree.modify(left, right - 1, -1);
106    }
107}
108
109/**
110 * Your RangeModule object will be instantiated and called as follows:
111 * RangeModule obj = new RangeModule();
112 * obj.addRange(left, right);
113 * boolean param_2 = obj.queryRange(left, right);
114 * obj.removeRange(left, right);
115 */
116

1#include <cstddef>
2
3// Templated caching mechanism for objects to reduce frequent allocations.
4template <class T>
5class CachedObj {
6public:
7    void* operator new(size_t sz) {
8        // If the pool is empty, fill it.
9        if (!head) {
10            T* array = new T[SIZE];
11            for (size_t i = 0; i < SIZE; ++i) {
12                add(array + i);
13            }
14        }
15        // Take a node from the front of the pool.
16        T* ptr = head;
17        head = head->CachedObj<T>::next;
18        return ptr;
19    }
20
21    void operator delete(void* ptr, size_t) {
22        // Return the node to the pool.
23        if (ptr) {
24            add(static_cast<T*>(ptr));
25        }
26    }
27
28    virtual ~CachedObj() {}
29
30protected:
31    T* next; // Next element in the cache.
32
33private:
34    static T* head; // Start of the object cache linked list.
35    static const size_t SIZE; // Size of a preallocated chunk of objects.
36
37    // Adds a new object to the object cache.
38    static void add(T* p) {
39        p->CachedObj<T>::next = head;
40        head = p;
41    }
42};
43
44// Static member initialization for CachedObj template.
45template <class T>
46T* CachedObj<T>::head = 0;
47template <class T>
48const size_t CachedObj<T>::SIZE = 10000;
49
50// Node used in the SegmentTree; specialized to benefit from CachedObj memory optimizations.
51class Node : public CachedObj<Node> {
52public:
53    Node* left;  // Pointer to left child
54    Node* right; // Pointer to right child
55    int value;   // Value representing the state of the segment
56    bool valid;  // Flag to mark valid segments
57};
58
59// Segment Tree implementation for range management.
60class SegmentTree {
61private:
62    Node* root; // Root node of the segment tree.
63
64public:
65    // Constructor initializes the root.
66    SegmentTree() {
67        root = new Node();
68    }
69
70    // Wrapper for modify operation.
71    void modify(int left, int right, int value) {
72        modify(left, right, value, 1, 1e9, root);
73    }
74
75    // Modify the range [left, right] with a value in the segment tree.
76    void modify(int left, int right, int value, int l, int r, Node* node) {
77        if (l >= left && r <= right) {
78            node->valid = (value == 1);
79            node->value = value;
80            return;
81        }
82        pushdown(node);
83        int mid = (l + r) >> 1; // Find the mid point
84        if (left <= mid)
85            modify(left, right, value, l, mid, node->left);
86        if (right > mid)
87            modify(left, right, value, mid + 1, r, node->right);
88        pushup(node);
89    }
90
91    // Wrapper for the query operation.
92    bool query(int left, int right) {
93        return query(left, right, 1, 1e9, root);
94    }
95
96    // Query the range [left, right] in the segment tree.
97    bool query(int left, int right, int l, int r, Node* node) {
98        if (l >= left && r <= right) return node->valid;
99        pushdown(node);
100        int mid = (l + r) >> 1; // Find the mid point
101        bool result = true;
102        if (left <= mid)
103            result = result && query(left, right, l, mid, node->left);
104        if (right > mid)
105            result = result && query(left, right, mid + 1, r, node->right);
106        return result;
107    }
108
109    // Push up the information to parent nodes after recursive updates.
110    void pushup(Node* node) {
111        node->valid = (node->left && node->left->valid &&
112                       node->right && node->right->valid);
113    }
114
115    // Push down the lazy propagation values to children nodes before recursion.
116    void pushdown(Node* node) {
117        if (!node->left) node->left = new Node();
118        if (!node->right) node->right = new Node();
119        if (node->value) {
120            node->left->value = node->right->value = node->value;
121            node->left->valid = node->right->valid = (node->value == 1);
122            node->value = 0;
123        }
124    }
125};
126
127// RangeModule class to represent a range system using a SegmentTree.
128class RangeModule {
129public:
130    // Pointer to the internal SegmentTree.
131    SegmentTree* tree;
132
133    // Constructor initializes the tree.
134    RangeModule() {
135        tree = new SegmentTree();
136    }
137
138    // Add a range to the SegmentTree.
139    void addRange(int left, int right) {
140        tree->modify(left, right - 1, 1);
141    }
142
143    // Query a range to see if it's fully contained.
144    bool queryRange(int left, int right) {
145        return tree->query(left, right - 1);
146    }
147
148    // Remove a range from the SegmentTree.
149    void removeRange(int left, int right) {
150        tree->modify(left, right - 1, -1);
151    }
152};
153
154// Usage example:
155// RangeModule* obj = new RangeModule();
156// obj->addRange(left, right);
157// bool param_2 = obj->queryRange(left, right);
158// obj->removeRange(left, right);
159

1// The size of a preallocated chunk of objects.
2const SIZE: number = 10000;
3
4// Node used in the SegmentTree; benefits from the object pool memory optimization.
5class Node {
6  left: Node | null = null;  // Pointer to the left child.
7  right: Node | null = null; // Pointer to the right child.
8  value: number = 0;         // Value representing the state of the segment.
9  valid: boolean = false;    // Flag to mark valid segments.
10
11  // Constructor
12  constructor() {}
13
14  // Static pool to serve as a cache for Node instances to reduce frequent allocations.
15  static pool: Node[] = [];
16
17  // Overriding the new operator for allocating from the pool.
18  static new(): Node {
19    // If the pool is empty, fill it.
20    if (Node.pool.length === 0) {
21      for (let i = 0; i < SIZE; ++i) {
22        Node.pool.push(new Node());
23      }
24    }
25    // Take a node from the pool.
26    return Node.pool.pop() as Node;
27  }
28
29  // Overriding the delete operator for returning to the pool.
30  static delete(node: Node): void {
31    // Return the node to the pool.
32    if (node) {
33      Node.pool.push(node);
34    }
35  }
36}
37
38// Segment Tree implementation for range management.
39class SegmentTree {
40  root: Node; // Root node of the segment tree.
41
42  // Constructor initializes the root.
43  constructor() {
44    this.root = Node.new();
45  }
46
47  // Modify the range [left, right] with a value in the segment tree.
48  private modify(left: number, right: number, value: number, l: number = 1, r: number = 1e9, node: Node = this.root): void {
49    if (l >= left && r <= right) {
50      node.valid = (value === 1);
51      node.value = value;
52      return;
53    }
54    this.pushdown(node);
55    let mid = (l + r) >> 1; // Find the midpoint.
56    if (left <= mid)
57      this.modify(left, right, value, l, mid, node.left!);
58    if (right > mid)
59      this.modify(left, right, value, mid + 1, r, node.right!);
60    this.pushup(node);
61  }
62
63  // Query the range [left, right] in the segment tree.
64  private query(left: number, right: number, l: number = 1, r: number = 1e9, node: Node = this.root): boolean {
65    if (l >= left && r <= right) return node.valid;
66    this.pushdown(node);
67    let mid = (l + r) >> 1; // Find the midpoint.
68    let result = true;
69    if (left <= mid)
70      result = result && this.query(left, right, l, mid, node.left!);
71    if (right > mid)
72      result = result && this.query(left, right, mid + 1, r, node.right!);
73    return result;
74  }
75
76  // Push up the information to parent nodes after recursive updates.
77  private pushup(node: Node): void {
78    node.valid = (node.left && node.left.valid &&
79                  node.right && node.right.valid);
80  }
81
82  // Push down the lazy propagation values to children nodes before recursion.
83  private pushdown(node: Node): void {
84    if (!node.left) node.left = Node.new();
85    if (!node.right) node.right = Node.new();
86    if (node.value) {
87      node.left.value = node.right.value = node.value;
88      node.left.valid = node.right.valid = (node.value === 1);
89      node.value = 0;
90    }
91  }
92}
93
94// RangeModule class to represent a range system using a SegmentTree.
95class RangeModule {
96  tree: SegmentTree;
97
98  // Constructor initializes the tree.
99  constructor() {
100    this.tree = new SegmentTree();
101  }
102
103  // Add a range to the SegmentTree.
104  addRange(left: number, right: number): void {
105    this.tree.modify(left, right - 1, 1);
106  }
107
108  // Query a range to see if it's fully contained.
109  queryRange(left: number, right: number): boolean {
110    return this.tree.query(left, right - 1);
111  }
112
113  // Remove a range from the SegmentTree.
114  removeRange(left: number, right: number): void {
115    this.tree.modify(left, right - 1, -1);
116  }
117}
118
119// Addresses standard memory de-allocation needs for Nodes after usage
120function deleteNodes(): void {
121  while (Node.pool.length) Node.delete(Node.pool.pop()!);
122}
123
124// Usage example:
125const module = new RangeModule();
126module.addRange(1, 10);
127const isRangeContained = module.queryRange(2, 9);
128module.removeRange(1, 10);
129deleteNodes(); // Clean-up Nodes from the pool when done
130

Time and Space Complexity

Time Complexity:

For the SegmentTree methods, let's analyze the time complexity:

modify(left, right, v):
- The time complexity of this function can be considered as O(log(range)) where range is the maximum value that the segment tree handles (in this case, range is int(1e9) by default). Despite the large range, actual complexity depends on the height of the segment tree given by O(log(n)) where n is the number of intervals added or removed since the tree becomes finer only in the areas that are modified.
query(left, right):
- The time complexity is O(log(range)) for the same reasons as the modify function, with actual complexity depending on the interval's distribution and the number of nodes created in those regions.
pushup(node):
- This has a constant time complexity of O(1) as it is just updating the value of the current node based on its children.
pushdown(node):
- Also operates in O(1) in terms of the direct operation it performs, though it can trigger the lazy creation of child nodes not previously accessed.

In the context of the RangeModule:

addRange(left, right), queryRange(left, right), removeRange(left, right) each make a call to modify(left, right, v) and query(left, right) on the SegmentTree, so they inherit the same time complexity.

Space Complexity:

The space complexity of the entire data structure is O(m) where m is the number of distinct intervals that have been added or removed. This is because new nodes in the tree are only created when a range is modified, which means the tree is sparse and doesn't necessarily contain a node for every possible value within the range.

Please note, the complexity analysis is given under the assumption that ranges do not tightly cover the entire possible range, meaning it is assuming sparsity typical of use-cases for segment trees, which allows us to consider complexities in terms of the number of modifications (n or m) rather than the total covered range (int(1e9)).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function call

Determine return value

Determine how many recursive calls will be made

Tracing the recursive calls