Facebook Pixel

715. Range Module

HardDesignSegment TreeOrdered Set
Leetcode Link

Problem Description

You need to design a data structure called Range Module that tracks ranges of numbers. The ranges are represented as half-open intervals [left, right), which means they include all real numbers x where left <= x < right (includes left but excludes right).

The Range Module should support the following operations:

  1. RangeModule(): Initializes an empty range module.

  2. addRange(int left, int right): Adds the half-open interval [left, right) to the module. This means you start tracking all numbers in this range. If the new interval overlaps with existing tracked intervals, they should be merged - any numbers in [left, right) that aren't already tracked should now be tracked.

  3. queryRange(int left, int right): Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise. The entire range must be covered for this to return true.

  4. removeRange(int left, int right): Stops tracking all real numbers in the half-open interval [left, right). This removes the specified range from the tracked intervals, potentially splitting existing intervals.

For example:

  • If you add range [10, 20) and then add [15, 25), the module tracks [10, 25).
  • If you're tracking [10, 30) and remove [15, 20), you'll be left tracking [10, 15) and [20, 30).
  • A query for [15, 17) returns true only if all numbers from 15 (inclusive) to 17 (exclusive) are being tracked.
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we need to efficiently manage interval operations (add, remove, query), we should think about data structures that can handle range updates and queries efficiently. The key insight is that we're dealing with continuous ranges that can overlap, merge, or split.

Initially, we might consider maintaining a sorted list of disjoint intervals. While this works, operations like merging overlapping intervals or splitting intervals during removal can be complex and potentially O(n) in the worst case.

A segment tree is particularly well-suited for this problem because:

  1. Range operations are natural: Segment trees are designed specifically for range queries and updates. Each node represents an interval, making it intuitive to track whether ranges are covered.

  2. Efficient updates: Instead of modifying every single point in a range, we can mark entire subtrees as "tracked" or "not tracked" using lazy propagation. This gives us O(log n) complexity for updates.

  3. Handling the large range: The problem doesn't specify bounds, but the solution assumes a range of [1, 10^9]. A regular array would be too memory-intensive. A dynamic segment tree only creates nodes as needed, making it memory-efficient.

The key realization is that we can use a boolean value at each node to indicate whether that entire range is being tracked. With lazy propagation, we can defer updates until necessary:

  • When adding a range, we mark nodes as tracked (add = 1)
  • When removing a range, we mark nodes as not tracked (add = -1)
  • The lazy value propagates down only when we need to traverse deeper into the tree

This approach transforms what could be complex interval manipulation into simple tree traversal with lazy updates, achieving O(log n) time complexity for all operations.

Learn more about Segment Tree patterns.

Solution Approach

The solution implements a dynamic segment tree with lazy propagation to efficiently handle range operations. Let's walk through the key components:

Node Structure

Each node in the segment tree contains:

  • left, right: Pointers to child nodes (created dynamically)
  • add: Lazy propagation flag (1 for add, -1 for remove, 0 for no pending operation)
  • v: Boolean indicating if the entire range represented by this node is tracked

Core Operations

1. Modify Operation (modify) This handles both addRange and removeRange:

  • Takes parameters: left, right (target range), v (1 for add, -1 for remove)
  • If current node's range [l, r] is completely within target range [left, right]:
    • Apply the operation directly using lazy propagation
    • Set node.add and update node.v
  • Otherwise, push down any pending updates and recursively modify children
  • The range is split at mid = (l + r) >> 1
  • After recursion, push up to update parent based on children's states

2. Query Operation (query) Checks if a range is fully tracked:

  • If current node's range is completely within query range, return node.v
  • Otherwise, push down pending updates and recursively query children
  • Returns true only if all queried portions are tracked

3. Lazy Propagation Helpers

pushdown: Propagates pending updates to children

  • Creates child nodes if they don't exist (dynamic allocation)
  • Transfers the add value to children
  • Updates children's v values based on the operation
  • Clears the current node's add flag

pushup: Updates parent node based on children

  • A node is tracked only if both children exist and are tracked
  • Uses node.v = node.left.v and node.right.v

RangeModule Integration

The main class wraps the segment tree:

  • addRange(left, right): Calls modify(left, right-1, 1)
  • removeRange(left, right): Calls modify(left, right-1, -1)
  • queryRange(left, right): Calls query(left, right-1)

Note: The implementation converts half-open intervals [left, right) to closed intervals [left, right-1] for the segment tree operations.

Time & Space Complexity

  • Time: O(log n) per operation where n is the range size (10^9)
  • Space: O(m log n) where m is the number of operations, due to dynamic node creation

The dynamic allocation ensures we only create nodes for ranges that are actually accessed, making this approach memory-efficient despite the large potential range.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's walk through a sequence of operations to see how the dynamic segment tree handles range tracking:

Initial State: Empty tree with range [1, 10^9]

Operation 1: addRange(10, 20)

  • We want to track interval [10, 20)
  • The segment tree calls modify(10, 19, 1) (converting to closed interval)
  • Starting from root [1, 10^9]:
    • Not fully contained, so split at mid = 5×10^8
    • Recursively go left to [1, 5×10^8]
    • Continue splitting until reaching a node that can represent [10, 19]
    • Mark this node with v = true and add = 1 (lazy flag)
  • Result: Range [10, 19] is now tracked

Operation 2: addRange(15, 25)

  • We want to track interval [15, 25)
  • The segment tree calls modify(15, 24, 1)
  • The tree traversal finds:
    • [15, 19] overlaps with existing tracked range [10, 19]
    • [20, 24] is a new range to track
  • After this operation, we effectively have [10, 24] tracked
  • The tree structure now has nodes representing these merged ranges

Operation 3: queryRange(12, 18)

  • We want to check if [12, 18) is fully tracked
  • The segment tree calls query(12, 17)
  • Starting from root:
    • Navigate down to find nodes covering [12, 17]
    • Push down any lazy updates along the path
    • Since [12, 17] is within the tracked range [10, 24], return true

Operation 4: removeRange(14, 16)

  • We want to stop tracking [14, 16)
  • The segment tree calls modify(14, 15, -1)
  • This splits the tracked range:
    • [10, 13] remains tracked
    • [14, 15] is marked as not tracked (v = false)
    • [16, 24] remains tracked
  • The tree handles this by:
    • Finding the node covering [14, 15]
    • Setting its add = -1 and v = false
    • Using pushup to update parent nodes

Operation 5: queryRange(13, 15)

  • We want to check if [13, 15) is fully tracked
  • The segment tree calls query(13, 14)
  • The query finds:
    • [13, 13] is tracked (part of [10, 13])
    • [14, 14] is NOT tracked (was removed)
  • Returns false because not all of [13, 14] is tracked

The key insight is that the segment tree dynamically creates nodes only for the ranges we actually use, avoiding the need to pre-allocate nodes for the entire [1, 10^9] range. The lazy propagation ensures we don't update every affected node immediately, but only when necessary during subsequent operations.

Solution Implementation

1class SegmentTreeNode:
2    """Node for the dynamic segment tree."""
3    __slots__ = ['left', 'right', 'lazy_tag', 'is_covered']
4  
5    def __init__(self):
6        self.left = None  # Left child node
7        self.right = None  # Right child node
8        self.lazy_tag = 0  # Lazy propagation tag: 1 for add, -1 for remove, 0 for none
9        self.is_covered = False  # Whether this range is fully covered
10
11
12class DynamicSegmentTree:
13    """Dynamic segment tree for range operations."""
14    __slots__ = ['root']
15  
16    def __init__(self):
17        self.root = SegmentTreeNode()
18  
19    def modify(self, query_left: int, query_right: int, operation: int, 
20               tree_left: int = 1, tree_right: int = 10**9, node: SegmentTreeNode = None) -> None:
21        """
22        Modify a range in the segment tree.
23      
24        Args:
25            query_left: Left boundary of the query range
26            query_right: Right boundary of the query range
27            operation: 1 for add operation, -1 for remove operation
28            tree_left: Left boundary of current tree node's range
29            tree_right: Right boundary of current tree node's range
30            node: Current tree node
31        """
32        if node is None:
33            node = self.root
34      
35        # If current range is completely within query range
36        if tree_left >= query_left and tree_right <= query_right:
37            if operation == 1:
38                # Mark range as covered
39                node.lazy_tag = 1
40                node.is_covered = True
41            else:
42                # Mark range as not covered
43                node.lazy_tag = -1
44                node.is_covered = False
45            return
46      
47        # Push down lazy tag before going to children
48        self._push_down(node)
49      
50        # Recursively update children
51        mid = (tree_left + tree_right) >> 1
52        if query_left <= mid:
53            self.modify(query_left, query_right, operation, tree_left, mid, node.left)
54        if query_right > mid:
55            self.modify(query_left, query_right, operation, mid + 1, tree_right, node.right)
56      
57        # Update current node based on children
58        self._push_up(node)
59  
60    def query(self, query_left: int, query_right: int, 
61              tree_left: int = 1, tree_right: int = 10**9, node: SegmentTreeNode = None) -> bool:
62        """
63        Query whether a range is fully covered.
64      
65        Args:
66            query_left: Left boundary of the query range
67            query_right: Right boundary of the query range
68            tree_left: Left boundary of current tree node's range
69            tree_right: Right boundary of current tree node's range
70            node: Current tree node
71          
72        Returns:
73            True if the entire range is covered, False otherwise
74        """
75        if node is None:
76            node = self.root
77      
78        # If current range is completely within query range
79        if tree_left >= query_left and tree_right <= query_right:
80            return node.is_covered
81      
82        # Push down lazy tag before querying children
83        self._push_down(node)
84      
85        # Query children and combine results
86        mid = (tree_left + tree_right) >> 1
87        result = True
88      
89        if query_left <= mid:
90            result = result and self.query(query_left, query_right, tree_left, mid, node.left)
91        if query_right > mid:
92            result = result and self.query(query_left, query_right, mid + 1, tree_right, node.right)
93      
94        return result
95  
96    def _push_up(self, node: SegmentTreeNode) -> None:
97        """
98        Update parent node based on children nodes.
99      
100        Args:
101            node: Current node to update
102        """
103        # A node is covered only if both children exist and are covered
104        node.is_covered = bool(node.left and node.left.is_covered and 
105                              node.right and node.right.is_covered)
106  
107    def _push_down(self, node: SegmentTreeNode) -> None:
108        """
109        Push down lazy tag to children nodes.
110      
111        Args:
112            node: Current node whose lazy tag needs to be pushed down
113        """
114        # Create children if they don't exist
115        if node.left is None:
116            node.left = SegmentTreeNode()
117        if node.right is None:
118            node.right = SegmentTreeNode()
119      
120        # Push down lazy tag if it exists
121        if node.lazy_tag:
122            # Apply lazy tag to children
123            node.left.lazy_tag = node.right.lazy_tag = node.lazy_tag
124            node.left.is_covered = (node.lazy_tag == 1)
125            node.right.is_covered = (node.lazy_tag == 1)
126            # Clear current node's lazy tag
127            node.lazy_tag = 0
128
129
130class RangeModule:
131    """
132    Module for managing ranges with add, query, and remove operations.
133    """
134  
135    def __init__(self):
136        self.tree = DynamicSegmentTree()
137  
138    def addRange(self, left: int, right: int) -> None:
139        """
140        Add a range [left, right) to the module.
141      
142        Args:
143            left: Start of the range (inclusive)
144            right: End of the range (exclusive)
145        """
146        # Convert to inclusive range [left, right-1]
147        self.tree.modify(left, right - 1, 1)
148  
149    def queryRange(self, left: int, right: int) -> bool:
150        """
151        Check if the range [left, right) is fully covered.
152      
153        Args:
154            left: Start of the range (inclusive)
155            right: End of the range (exclusive)
156          
157        Returns:
158            True if the entire range is covered, False otherwise
159        """
160        # Convert to inclusive range [left, right-1]
161        return self.tree.query(left, right - 1)
162  
163    def removeRange(self, left: int, right: int) -> None:
164        """
165        Remove a range [left, right) from the module.
166      
167        Args:
168            left: Start of the range (inclusive)
169            right: End of the range (exclusive)
170        """
171        # Convert to inclusive range [left, right-1]
172        self.tree.modify(left, right - 1, -1)
173
174
175# Your RangeModule object will be instantiated and called as such:
176# obj = RangeModule()
177# obj.addRange(left,right)
178# param_2 = obj.queryRange(left,right)
179# obj.removeRange(left,right)
180
1/**
2 * Node class for the Segment Tree
3 * Represents a node in the dynamic segment tree
4 */
5class Node {
6    Node left;          // Left child node
7    Node right;         // Right child node
8    int lazyTag;        // Lazy propagation tag: 1 for add, -1 for remove, 0 for no operation
9    boolean isTracked;  // Whether this range is fully tracked
10}
11
12/**
13 * Dynamic Segment Tree implementation
14 * Supports range update and range query operations
15 */
16class SegmentTree {
17    private static final int MIN_RANGE = 1;
18    private static final int MAX_RANGE = (int) 1e9;
19    private Node root = new Node();
20
21    public SegmentTree() {
22    }
23
24    /**
25     * Public method to modify a range
26     * @param left Left boundary of the range to modify
27     * @param right Right boundary of the range to modify
28     * @param value 1 to track the range, -1 to untrack the range
29     */
30    public void modify(int left, int right, int value) {
31        modify(left, right, value, MIN_RANGE, MAX_RANGE, root);
32    }
33
34    /**
35     * Private recursive method to modify a range in the segment tree
36     * @param targetLeft Left boundary of target range
37     * @param targetRight Right boundary of target range
38     * @param value Update value (1 for track, -1 for untrack)
39     * @param currentLeft Current node's left boundary
40     * @param currentRight Current node's right boundary
41     * @param node Current node being processed
42     */
43    private void modify(int targetLeft, int targetRight, int value, 
44                       int currentLeft, int currentRight, Node node) {
45        // If current range is completely within target range
46        if (currentLeft >= targetLeft && currentRight <= targetRight) {
47            node.isTracked = (value == 1);
48            node.lazyTag = value;
49            return;
50        }
51      
52        // Push down lazy updates before continuing
53        pushDown(node);
54      
55        int mid = (currentLeft + currentRight) >> 1;
56      
57        // Recursively update left subtree if needed
58        if (targetLeft <= mid) {
59            modify(targetLeft, targetRight, value, currentLeft, mid, node.left);
60        }
61      
62        // Recursively update right subtree if needed
63        if (targetRight > mid) {
64            modify(targetLeft, targetRight, value, mid + 1, currentRight, node.right);
65        }
66      
67        // Update current node based on children
68        pushUp(node);
69    }
70
71    /**
72     * Public method to query if a range is fully tracked
73     * @param left Left boundary of the query range
74     * @param right Right boundary of the query range
75     * @return true if the entire range is tracked, false otherwise
76     */
77    public boolean query(int left, int right) {
78        return query(left, right, MIN_RANGE, MAX_RANGE, root);
79    }
80
81    /**
82     * Private recursive method to query a range in the segment tree
83     * @param targetLeft Left boundary of target range
84     * @param targetRight Right boundary of target range
85     * @param currentLeft Current node's left boundary
86     * @param currentRight Current node's right boundary
87     * @param node Current node being processed
88     * @return true if the queried range is fully tracked
89     */
90    private boolean query(int targetLeft, int targetRight, 
91                         int currentLeft, int currentRight, Node node) {
92        // If current range is completely within target range
93        if (currentLeft >= targetLeft && currentRight <= targetRight) {
94            return node.isTracked;
95        }
96      
97        // Push down lazy updates before querying
98        pushDown(node);
99      
100        int mid = (currentLeft + currentRight) >> 1;
101        boolean result = true;
102      
103        // Query left subtree if needed
104        if (targetLeft <= mid) {
105            result = result && query(targetLeft, targetRight, currentLeft, mid, node.left);
106        }
107      
108        // Query right subtree if needed
109        if (targetRight > mid) {
110            result = result && query(targetLeft, targetRight, mid + 1, currentRight, node.right);
111        }
112      
113        return result;
114    }
115
116    /**
117     * Update parent node based on children nodes
118     * @param node The node to update
119     */
120    private void pushUp(Node node) {
121        node.isTracked = node.left != null && node.left.isTracked && 
122                        node.right != null && node.right.isTracked;
123    }
124
125    /**
126     * Push down lazy updates to children nodes
127     * Creates children nodes if they don't exist
128     * @param node The node whose lazy updates need to be pushed down
129     */
130    private void pushDown(Node node) {
131        // Create children nodes if they don't exist
132        if (node.left == null) {
133            node.left = new Node();
134        }
135        if (node.right == null) {
136            node.right = new Node();
137        }
138      
139        // Apply lazy updates to children
140        if (node.lazyTag != 0) {
141            node.left.lazyTag = node.lazyTag;
142            node.right.lazyTag = node.lazyTag;
143            node.left.isTracked = (node.lazyTag == 1);
144            node.right.isTracked = (node.lazyTag == 1);
145            node.lazyTag = 0; // Clear the lazy tag
146        }
147    }
148}
149
150/**
151 * RangeModule class to manage ranges
152 * Supports adding, querying, and removing ranges
153 */
154class RangeModule {
155    private SegmentTree tree = new SegmentTree();
156
157    public RangeModule() {
158    }
159
160    /**
161     * Add a range [left, right) to be tracked
162     * @param left Inclusive left boundary
163     * @param right Exclusive right boundary
164     */
165    public void addRange(int left, int right) {
166        // Convert to inclusive range [left, right-1]
167        tree.modify(left, right - 1, 1);
168    }
169
170    /**
171     * Query if range [left, right) is fully tracked
172     * @param left Inclusive left boundary
173     * @param right Exclusive right boundary
174     * @return true if the entire range is tracked, false otherwise
175     */
176    public boolean queryRange(int left, int right) {
177        // Convert to inclusive range [left, right-1]
178        return tree.query(left, right - 1);
179    }
180
181    /**
182     * Remove a range [left, right) from tracking
183     * @param left Inclusive left boundary
184     * @param right Exclusive right boundary
185     */
186    public void removeRange(int left, int right) {
187        // Convert to inclusive range [left, right-1]
188        tree.modify(left, right - 1, -1);
189    }
190}
191
192/**
193 * Your RangeModule object will be instantiated and called as such:
194 * RangeModule obj = new RangeModule();
195 * obj.addRange(left,right);
196 * boolean param_2 = obj.queryRange(left,right);
197 * obj.removeRange(left,right);
198 */
199
1/**
2 * Memory pool implementation for efficient allocation/deallocation
3 * Uses a free list to reuse memory blocks
4 */
5template <class T>
6class CachedObj {
7public:
8    // Custom new operator that allocates from the memory pool
9    void* operator new(size_t s) {
10        // If free list is empty, allocate a new chunk
11        if (!head) {
12            T* chunk = new T[CHUNK_SIZE];
13            for (size_t i = 0; i < CHUNK_SIZE; ++i) {
14                addToFreeList(chunk + i);
15            }
16        }
17        // Get the first available object from free list
18        T* ptr = head;
19        head = head->CachedObj<T>::next;
20        return ptr;
21    }
22  
23    // Custom delete operator that returns object to the pool
24    void operator delete(void* ptr, size_t) {
25        if (ptr) {
26            addToFreeList(static_cast<T*>(ptr));
27        }
28    }
29  
30    virtual ~CachedObj() {}
31
32protected:
33    T* next;  // Pointer to next object in free list
34
35private:
36    static T* head;                    // Head of the free list
37    static const size_t CHUNK_SIZE;    // Number of objects to allocate at once
38  
39    // Add an object to the free list
40    static void addToFreeList(T* ptr) {
41        ptr->CachedObj<T>::next = head;
42        head = ptr;
43    }
44};
45
46// Static member initialization
47template <class T>
48T* CachedObj<T>::head = nullptr;
49template <class T>
50const size_t CachedObj<T>::CHUNK_SIZE = 10000;
51
52/**
53 * Segment tree node with memory pool optimization
54 */
55class Node : public CachedObj<Node> {
56public:
57    Node* left;     // Left child pointer
58    Node* right;    // Right child pointer
59    int lazyTag;    // Lazy propagation tag (1: add, -1: remove, 0: none)
60    bool covered;   // Whether this range is fully covered
61};
62
63/**
64 * Dynamic segment tree for range operations
65 * Supports lazy propagation and dynamic node creation
66 */
67class SegmentTree {
68private:
69    Node* root;
70    static const int MIN_RANGE = 1;
71    static const int MAX_RANGE = 1000000000;
72
73public:
74    SegmentTree() {
75        root = new Node();
76    }
77
78    // Public interface to modify a range
79    void modify(int left, int right, int value) {
80        modify(left, right, value, MIN_RANGE, MAX_RANGE, root);
81    }
82
83    // Public interface to query a range
84    bool query(int left, int right) {
85        return query(left, right, MIN_RANGE, MAX_RANGE, root);
86    }
87
88private:
89    /**
90     * Modify operation with lazy propagation
91     * @param left, right: target range to modify
92     * @param value: 1 for add, -1 for remove
93     * @param l, r: current node's range
94     * @param node: current node
95     */
96    void modify(int left, int right, int value, int l, int r, Node* node) {
97        // If current range is completely within target range
98        if (l >= left && r <= right) {
99            node->covered = (value == 1);
100            node->lazyTag = value;
101            return;
102        }
103      
104        // Ensure children exist and push down lazy tag
105        pushDown(node);
106      
107        int mid = (l + r) >> 1;
108        // Recursively modify left child if needed
109        if (left <= mid) {
110            modify(left, right, value, l, mid, node->left);
111        }
112        // Recursively modify right child if needed
113        if (right > mid) {
114            modify(left, right, value, mid + 1, r, node->right);
115        }
116      
117        // Update current node based on children
118        pushUp(node);
119    }
120
121    /**
122     * Query if a range is fully covered
123     * @param left, right: target range to query
124     * @param l, r: current node's range
125     * @param node: current node
126     * @return true if the entire range is covered
127     */
128    bool query(int left, int right, int l, int r, Node* node) {
129        // If current range is completely within target range
130        if (l >= left && r <= right) {
131            return node->covered;
132        }
133      
134        // Ensure children exist and push down lazy tag
135        pushDown(node);
136      
137        int mid = (l + r) >> 1;
138        bool result = true;
139      
140        // Query left child if needed
141        if (left <= mid) {
142            result = result && query(left, right, l, mid, node->left);
143        }
144        // Query right child if needed
145        if (right > mid) {
146            result = result && query(left, right, mid + 1, r, node->right);
147        }
148      
149        return result;
150    }
151
152    /**
153     * Update parent node based on children
154     */
155    void pushUp(Node* node) {
156        node->covered = node->left && node->left->covered && 
157                       node->right && node->right->covered;
158    }
159
160    /**
161     * Push down lazy tag to children and create children if needed
162     */
163    void pushDown(Node* node) {
164        // Create children nodes if they don't exist
165        if (!node->left) {
166            node->left = new Node();
167        }
168        if (!node->right) {
169            node->right = new Node();
170        }
171      
172        // Propagate lazy tag to children
173        if (node->lazyTag != 0) {
174            node->left->lazyTag = node->lazyTag;
175            node->right->lazyTag = node->lazyTag;
176            node->left->covered = (node->lazyTag == 1);
177            node->right->covered = (node->lazyTag == 1);
178            node->lazyTag = 0;
179        }
180    }
181};
182
183/**
184 * Range Module for managing integer ranges
185 * Supports adding, removing, and querying ranges
186 */
187class RangeModule {
188private:
189    SegmentTree* tree;
190
191public:
192    RangeModule() {
193        tree = new SegmentTree();
194    }
195
196    /**
197     * Add range [left, right) to the set
198     * Note: right is exclusive
199     */
200    void addRange(int left, int right) {
201        tree->modify(left, right - 1, 1);
202    }
203
204    /**
205     * Query if range [left, right) is fully covered
206     * Note: right is exclusive
207     */
208    bool queryRange(int left, int right) {
209        return tree->query(left, right - 1);
210    }
211
212    /**
213     * Remove range [left, right) from the set
214     * Note: right is exclusive
215     */
216    void removeRange(int left, int right) {
217        tree->modify(left, right - 1, -1);
218    }
219};
220
221/**
222 * Your RangeModule object will be instantiated and called as such:
223 * RangeModule* obj = new RangeModule();
224 * obj->addRange(left,right);
225 * bool param_2 = obj->queryRange(left,right);
226 * obj->removeRange(left,right);
227 */
228
1// Node structure for the segment tree
2interface SegmentNode {
3    leftChild: SegmentNode | null;
4    rightChild: SegmentNode | null;
5    lazyTag: number;  // Lazy propagation tag: 1 for add, -1 for remove, 0 for no operation
6    isCovered: boolean;  // Whether this range is fully covered
7}
8
9// Create a new segment tree node
10function createNode(): SegmentNode {
11    return {
12        leftChild: null,
13        rightChild: null,
14        lazyTag: 0,
15        isCovered: false
16    };
17}
18
19// Root of the segment tree
20let segmentTreeRoot: SegmentNode = createNode();
21
22// Push up: update parent node based on children
23function pushUp(node: SegmentNode): void {
24    node.isCovered = !!(
25        node.leftChild && 
26        node.leftChild.isCovered && 
27        node.rightChild && 
28        node.rightChild.isCovered
29    );
30}
31
32// Push down: propagate lazy tag to children
33function pushDown(node: SegmentNode): void {
34    // Create children if they don't exist
35    if (node.leftChild === null) {
36        node.leftChild = createNode();
37    }
38    if (node.rightChild === null) {
39        node.rightChild = createNode();
40    }
41  
42    // Propagate lazy tag if exists
43    if (node.lazyTag !== 0) {
44        node.leftChild.lazyTag = node.lazyTag;
45        node.rightChild.lazyTag = node.lazyTag;
46        node.leftChild.isCovered = node.lazyTag === 1;
47        node.rightChild.isCovered = node.lazyTag === 1;
48        node.lazyTag = 0;
49    }
50}
51
52// Modify a range in the segment tree
53function modifyRange(
54    targetLeft: number,
55    targetRight: number,
56    value: number,
57    currentLeft: number = 1,
58    currentRight: number = 1e9,
59    node: SegmentNode | null = null
60): void {
61    if (node === null) {
62        node = segmentTreeRoot;
63    }
64  
65    // If current range is completely within target range
66    if (currentLeft >= targetLeft && currentRight <= targetRight) {
67        node.isCovered = value === 1;
68        node.lazyTag = value;
69        return;
70    }
71  
72    pushDown(node);
73  
74    const mid = Math.floor((currentLeft + currentRight) / 2);
75  
76    // Recursively modify left subtree if needed
77    if (targetLeft <= mid) {
78        modifyRange(targetLeft, targetRight, value, currentLeft, mid, node.leftChild);
79    }
80  
81    // Recursively modify right subtree if needed
82    if (targetRight > mid) {
83        modifyRange(targetLeft, targetRight, value, mid + 1, currentRight, node.rightChild);
84    }
85  
86    pushUp(node);
87}
88
89// Query if a range is fully covered
90function queryRange(
91    targetLeft: number,
92    targetRight: number,
93    currentLeft: number = 1,
94    currentRight: number = 1e9,
95    node: SegmentNode | null = null
96): boolean {
97    if (node === null) {
98        node = segmentTreeRoot;
99    }
100  
101    // If current range is completely within target range
102    if (currentLeft >= targetLeft && currentRight <= targetRight) {
103        return node.isCovered;
104    }
105  
106    pushDown(node);
107  
108    const mid = Math.floor((currentLeft + currentRight) / 2);
109    let result = true;
110  
111    // Query left subtree if needed
112    if (targetLeft <= mid) {
113        result = result && queryRange(targetLeft, targetRight, currentLeft, mid, node.leftChild);
114    }
115  
116    // Query right subtree if needed
117    if (targetRight > mid) {
118        result = result && queryRange(targetLeft, targetRight, mid + 1, currentRight, node.rightChild);
119    }
120  
121    return result;
122}
123
124// Add a range [left, right)
125function addRange(left: number, right: number): void {
126    modifyRange(left, right - 1, 1);
127}
128
129// Query if range [left, right) is fully covered
130function queryRange(left: number, right: number): boolean {
131    return queryRange(left, right - 1);
132}
133
134// Remove a range [left, right)
135function removeRange(left: number, right: number): void {
136    modifyRange(left, right - 1, -1);
137}
138

Time and Space Complexity

Time Complexity: Each operation (addRange, queryRange, removeRange) has a time complexity of O(log n), where n is the data range (in this case 10^9).

The segment tree operations work by recursively dividing the range in half at each level. Since the tree height is bounded by log n, and each operation traverses at most two paths from root to leaf (due to the range potentially spanning across the middle point), the time complexity remains O(log n) per operation.

Space Complexity: The space complexity is O(m × log n), where m is the number of operations and n is the data range.

This implementation uses a dynamic segment tree with lazy node creation. Nodes are only created when needed during operations. In the worst case, each operation could create up to O(log n) new nodes along the path from root to the affected leaves. With m operations, the total number of nodes created can be at most O(m × log n).

The __slots__ optimization in the Node class helps reduce memory overhead per node, but doesn't change the asymptotic space complexity. Each node stores a constant amount of data (left pointer, right pointer, add value, and boolean v), so the space per node is O(1), making the total space complexity O(m × log n).

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

Common Pitfalls

1. Incorrect Handling of Half-Open Intervals

Pitfall: The most common mistake is forgetting to convert half-open intervals [left, right) to closed intervals [left, right-1] when working with the segment tree. This leads to off-by-one errors.

Example of the bug:

def addRange(self, left: int, right: int) -> None:
    # WRONG: Passing right directly instead of right-1
    self.tree.modify(left, right, 1)  # Bug!

Why it happens: The problem uses half-open intervals (excludes the right boundary), but segment trees typically work with closed intervals. If you pass right directly, you're including one extra element.

Solution: Always subtract 1 from the right boundary:

def addRange(self, left: int, right: int) -> None:
    # CORRECT: Convert [left, right) to [left, right-1]
    self.tree.modify(left, right - 1, 1)

2. Forgetting to Push Down Lazy Tags Before Querying Children

Pitfall: Not calling push_down before recursively querying or modifying children leads to stale data being used.

Example of the bug:

def query(self, query_left, query_right, tree_left, tree_right, node):
    if tree_left >= query_left and tree_right <= query_right:
        return node.is_covered
  
    # WRONG: Forgot to push down before querying children
    mid = (tree_left + tree_right) >> 1
    result = True
    if query_left <= mid:
        result = result and self.query(query_left, query_right, tree_left, mid, node.left)
    # ... rest of code

Why it happens: Lazy propagation defers updates. If you don't push down pending updates before accessing children, the children will have outdated information.

Solution: Always push down before accessing children:

def query(self, query_left, query_right, tree_left, tree_right, node):
    if tree_left >= query_left and tree_right <= query_right:
        return node.is_covered
  
    # CORRECT: Push down lazy tags first
    self._push_down(node)
  
    mid = (tree_left + tree_right) >> 1
    # ... rest of code

3. Incorrect Push-Up Logic

Pitfall: Setting node.is_covered = node.left.is_covered or node.right.is_covered instead of using and.

Example of the bug:

def _push_up(self, node):
    # WRONG: Using OR instead of AND
    node.is_covered = (node.left and node.left.is_covered) or \
                     (node.right and node.right.is_covered)

Why it happens: A range is only fully covered if ALL of it is covered. Using or would incorrectly mark a parent as covered when only part of its range is covered.

Solution: Use and to ensure both children are covered:

def _push_up(self, node):
    # CORRECT: Both children must exist and be covered
    node.is_covered = bool(node.left and node.left.is_covered and 
                          node.right and node.right.is_covered)

4. Not Handling Node Creation in Push-Down

Pitfall: Accessing node.left or node.right without checking if they exist first, causing AttributeError.

Example of the bug:

def _push_down(self, node):
    # WRONG: Directly accessing children without checking existence
    if node.lazy_tag:
        node.left.lazy_tag = node.lazy_tag  # Crash if node.left is None!
        node.right.lazy_tag = node.lazy_tag

Solution: Create children nodes if they don't exist:

def _push_down(self, node):
    # CORRECT: Create children first if needed
    if node.left is None:
        node.left = SegmentTreeNode()
    if node.right is None:
        node.right = SegmentTreeNode()
  
    if node.lazy_tag:
        node.left.lazy_tag = node.lazy_tag
        node.right.lazy_tag = node.lazy_tag
        # ... rest of code

5. Forgetting to Clear Lazy Tag After Pushing Down

Pitfall: Not resetting node.lazy_tag = 0 after propagating it to children, causing the same update to be applied multiple times.

Example of the bug:

def _push_down(self, node):
    if node.lazy_tag:
        node.left.lazy_tag = node.lazy_tag
        node.right.lazy_tag = node.lazy_tag
        # WRONG: Forgot to clear the lazy tag!
        # node.lazy_tag = 0  # Missing line

Solution: Always clear the lazy tag after propagation:

def _push_down(self, node):
    if node.lazy_tag:
        # ... propagate to children ...
        node.lazy_tag = 0  # CORRECT: Clear after propagation
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Recommended Readings

Segment Tree

Segment Tree Faster Range Queries For this article we want to introduce the idea of a Segment Tree Segment Trees allow us to quickly perform range queries as well as range updates Suppose we have an array and we want to know the sum of a particular range of numbers as well

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More