Facebook Pixel

2276. Count Integers in Intervals

HardDesignSegment TreeOrdered Set
Leetcode Link

Problem Description

You need to implement a data structure that maintains a collection of intervals and supports two operations:

  1. Add an interval: Given a range [left, right], add this interval to your collection. The interval includes all integers from left to right inclusive.

  2. Count unique integers: Return the total count of distinct integers that appear in at least one interval in your collection.

The key challenge is handling overlapping intervals efficiently. When you add a new interval, it might overlap with existing intervals, and you need to count each integer only once regardless of how many intervals contain it.

For example:

  • If you add intervals [1, 5] and [3, 7], the integers covered are {1, 2, 3, 4, 5, 6, 7}, so the count would be 7.
  • Adding another interval [2, 4] doesn't change the count since all integers in [2, 4] are already covered.

The solution uses a Segment Tree with Lazy Propagation to efficiently handle these operations:

  • The segment tree dynamically creates nodes as needed (dynamic opening) to handle the large range of possible values (up to 10^9)
  • Each node in the tree represents a range and stores how many integers in that range are covered
  • The add operation marks a range as fully covered using lazy propagation
  • The count operation queries the root to get the total number of covered integers
  • Lazy propagation ensures that updates are propagated down the tree only when necessary, maintaining O(log n) time complexity for both operations

The segment tree divides intervals recursively: each node [l, r] has a left child [l, mid] and right child [mid+1, r] where mid = (l + r) // 2. When an interval is added, the tree marks the appropriate nodes as covered and uses the add flag for lazy propagation to avoid unnecessary traversals.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

When we need to track which integers are covered by multiple intervals, the naive approach would be to maintain a set or array marking each covered integer. However, with values up to 10^9, this becomes impractical in terms of space.

The key insight is that we're dealing with continuous ranges rather than individual points. When we add an interval [left, right], we're essentially marking all integers in that range as "covered". This naturally leads us to think about data structures that efficiently handle range updates.

Consider what happens when we add overlapping intervals:

  • Adding [1, 5] covers 5 integers
  • Adding [3, 7] extends the coverage to 7 integers total (not 5 + 5 = 10)
  • The overlap [3, 5] should only be counted once

This suggests we need a way to:

  1. Mark ranges as covered
  2. Handle overlaps automatically
  3. Query the total coverage efficiently

A Segment Tree is perfect for this because:

  • It naturally represents ranges hierarchically
  • It can mark entire ranges as covered in O(log n) time
  • It automatically handles overlaps - once a range is marked as covered, marking it again doesn't change anything
  • It can sum up the total coverage by querying the root

The challenge with the large value range (10^9) is solved through dynamic opening - we only create tree nodes when we actually need them. Instead of pre-allocating a massive tree, we start with just the root node and create children on-demand during operations.

Lazy propagation is crucial for efficiency. When we mark a large range as covered, instead of immediately updating all descendant nodes, we just mark the current node with a "lazy" flag. This flag gets pushed down to children only when we need to access them later. This way, marking a range takes O(log n) time regardless of the range size.

The brilliance of this approach is that each node stores v - the count of covered integers in its range. When we mark a range [l, r] as covered, we simply set v = r - l + 1. The total count is just the v value at the root, which represents the entire possible range [1, 10^9].

Learn more about Segment Tree patterns.

Solution Approach

The implementation uses a Segment Tree with Dynamic Opening and Lazy Propagation. Let's walk through each component:

Node Structure

Each node in the segment tree contains:

  • left, right: Pointers to child nodes (initially None for dynamic opening)
  • l, r: The range boundaries this node represents
  • mid: The midpoint (l + r) // 2 for splitting the range
  • v: Count of covered integers in this range
  • add: Lazy propagation flag (1 if entire range is covered, 0 otherwise)

SegmentTree Class

Initialization: Creates only the root node covering the entire range [1, 10^9 + 1].

modify(l, r, v): Marks the range [l, r] as covered.

  1. If the current node's range is completely within [l, r], mark the entire node:
    • Set node.v = node.r - node.l + 1 (all integers in range are covered)
    • Set node.add = 1 for lazy propagation
    • Return early (no need to go deeper)
  2. Otherwise, push down any lazy updates and recursively modify children:
    • If l <= node.mid, modify the left subtree
    • If r > node.mid, modify the right subtree
  3. After modifying children, update current node's value using pushup()

query(l, r): Returns count of covered integers in range [l, r].

  1. If the current node's range is completely within [l, r], return node.v
  2. Otherwise, push down lazy updates and query relevant children:
    • Query left child if l <= node.mid
    • Query right child if r > node.mid
    • Sum the results

pushdown(node): Handles lazy propagation.

  1. Create child nodes if they don't exist (dynamic opening)
  2. If node.add != 0, propagate the update to children:
    • Set children's add flags to 1
    • Set children's values to their full range counts
    • Clear the current node's add flag

pushup(node): Updates parent value based on children.

  • Sets node.v = node.left.v + node.right.v

CountIntervals Class

Simply wraps the segment tree:

  • add(left, right): Calls tree.modify(left, right, 1) to mark range as covered
  • count(): Calls tree.query(1, 10^9) to get total covered integers

Time Complexity

  • add(): O(log n) where n is the range size (up to 10^9)
  • count(): O(log n) for querying the full range

Space Complexity

  • O(m × log n) where m is the number of add operations, as we only create nodes when needed

The key efficiency comes from:

  1. Dynamic opening - only creating nodes when accessed
  2. Lazy propagation - deferring updates until necessary
  3. Range representation - storing counts instead of individual integers

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 concrete example to understand how the segment tree handles interval operations.

Initial Setup: We start with an empty segment tree. The root node represents the range [1, 1000000000] with v = 0 (no integers covered).

Step 1: Add interval [2, 5]

Starting from the root [1, 1000000000]:

  • Since [2, 5] doesn't cover the entire root range, we need to recurse
  • Calculate mid = (1 + 1000000000) // 2 = 500000000
  • Since 5 <= 500000000, we only go left
  • Create left child node [1, 500000000] dynamically
  • Continue recursing down until we find a node that [2, 5] completely covers

Eventually, we reach a node representing range [2, 5] (after several recursive splits):

  • Set this node's v = 5 - 2 + 1 = 4 (four integers covered)
  • Set add = 1 (lazy flag indicating full coverage)
  • Propagate the count back up: root's v becomes 4

Step 2: Add interval [4, 8]

Starting from root [1, 1000000000] with v = 4:

  • [4, 8] doesn't cover the entire range, so recurse
  • This time we need to traverse to nodes that overlap with [4, 8]

When we reach the previously created nodes:

  • The node for [2, 5] partially overlaps with [4, 8]
  • We push down the lazy update (creating children if needed)
  • The overlap [4, 5] is already marked as covered
  • We mark the new portion [6, 8] as covered (3 new integers)

After propagation back up:

  • Root's v = 4 + 3 = 7 (integers 2, 3, 4, 5, 6, 7, 8 are covered)

Step 3: Add interval [3, 6]

Starting from root with v = 7:

  • [3, 6] overlaps with existing covered ranges
  • As we traverse down, we find:
    • [3, 5] is already covered (from previous intervals)
    • [6, 6] is already covered (from interval [4, 8])
  • No new integers are added

Root's v remains 7.

Step 4: Count operation

Query the root node [1, 1000000000]:

  • Simply return root's v = 7

Key Observations:

  1. Dynamic Node Creation: We only created nodes for ranges we actually needed (around [2, 8]), not the entire billion-integer range.

  2. Lazy Propagation in Action: When we marked [2, 5] as covered, we didn't immediately create all child nodes. We just set add = 1 and v = 4. Children were created only when needed for the [4, 8] operation.

  3. Automatic Overlap Handling: When adding [3, 6], the tree automatically recognized that all these integers were already covered. No double-counting occurred.

  4. Efficient Counting: Getting the total count is just reading the root's v value - O(1) after the tree is built.

The tree structure after these operations (simplified) might look like:

                Root [1, 10^9]: v=7
                      /
            [1, 500M]: v=7
                /
          [1, 250K]: v=7
              /
        ... (more nodes)
            /
      [2, 8]: v=7
      (with appropriate child nodes)

This demonstrates how the segment tree efficiently handles large ranges by only creating necessary nodes and using lazy propagation to defer updates until needed.

Solution Implementation

1class Node:
2    """Node class for dynamic segment tree."""
3    __slots__ = ("left", "right", "l", "r", "mid", "v", "add")
4
5    def __init__(self, left_bound: int, right_bound: int):
6        """
7        Initialize a segment tree node.
8      
9        Args:
10            left_bound: Left boundary of the interval
11            right_bound: Right boundary of the interval
12        """
13        self.left = None  # Left child node
14        self.right = None  # Right child node
15        self.l = left_bound  # Left boundary of current segment
16        self.r = right_bound  # Right boundary of current segment
17        self.mid = (left_bound + right_bound) // 2  # Midpoint for splitting
18        self.v = 0  # Value stored in this node (count of covered integers)
19        self.add = 0  # Lazy propagation flag (1 if entire range should be marked)
20
21
22class SegmentTree:
23    """Dynamic segment tree for range updates and queries."""
24  
25    def __init__(self):
26        """Initialize segment tree with range [1, 10^9]."""
27        self.root = Node(1, int(1e9) + 1)
28
29    def modify(self, left: int, right: int, value: int, node: Node = None) -> None:
30        """
31        Update range [left, right] with given value.
32      
33        Args:
34            left: Left boundary of update range
35            right: Right boundary of update range
36            value: Value to set (1 for marking as covered)
37            node: Current node in recursion (defaults to root)
38        """
39        if node is None:
40            node = self.root
41          
42        # Invalid range
43        if left > right:
44            return
45          
46        # Current segment is completely within update range
47        if node.l >= left and node.r <= right:
48            # Mark entire segment as covered
49            node.v = node.r - node.l + 1
50            node.add = value
51            return
52          
53        # Push down lazy updates before going deeper
54        self.pushdown(node)
55      
56        # Recursively update left child if needed
57        if left <= node.mid:
58            self.modify(left, right, value, node.left)
59          
60        # Recursively update right child if needed
61        if right > node.mid:
62            self.modify(left, right, value, node.right)
63          
64        # Update current node value based on children
65        self.pushup(node)
66
67    def query(self, left: int, right: int, node: Node = None) -> int:
68        """
69        Query the count of covered integers in range [left, right].
70      
71        Args:
72            left: Left boundary of query range
73            right: Right boundary of query range
74            node: Current node in recursion (defaults to root)
75          
76        Returns:
77            Count of covered integers in the range
78        """
79        if node is None:
80            node = self.root
81          
82        # Invalid range
83        if left > right:
84            return 0
85          
86        # Current segment is completely within query range
87        if node.l >= left and node.r <= right:
88            return node.v
89          
90        # Push down lazy updates before querying children
91        self.pushdown(node)
92      
93        result = 0
94      
95        # Query left child if needed
96        if left <= node.mid:
97            result += self.query(left, right, node.left)
98          
99        # Query right child if needed
100        if right > node.mid:
101            result += self.query(left, right, node.right)
102          
103        return result
104
105    def pushup(self, node: Node) -> None:
106        """
107        Update parent node value based on children values.
108      
109        Args:
110            node: Node to update
111        """
112        node.v = node.left.v + node.right.v
113
114    def pushdown(self, node: Node) -> None:
115        """
116        Push down lazy updates to children and create children if needed.
117      
118        Args:
119            node: Node whose lazy updates need to be pushed down
120        """
121        # Create children nodes if they don't exist (dynamic segment tree)
122        if node.left is None:
123            node.left = Node(node.l, node.mid)
124        if node.right is None:
125            node.right = Node(node.mid + 1, node.r)
126          
127        # Push down lazy update if exists
128        if node.add != 0:
129            left_child, right_child = node.left, node.right
130          
131            # Apply lazy update to children
132            left_child.add = node.add
133            right_child.add = node.add
134          
135            # Update children values (mark entire range as covered)
136            left_child.v = left_child.r - left_child.l + 1
137            right_child.v = right_child.r - right_child.l + 1
138          
139            # Clear lazy update from current node
140            node.add = 0
141
142
143class CountIntervals:
144    """Class to count total number of integers covered by added intervals."""
145  
146    def __init__(self):
147        """Initialize with an empty segment tree."""
148        self.tree = SegmentTree()
149
150    def add(self, left: int, right: int) -> None:
151        """
152        Add interval [left, right] to the collection.
153      
154        Args:
155            left: Left boundary of interval
156            right: Right boundary of interval
157        """
158        self.tree.modify(left, right, 1)
159
160    def count(self) -> int:
161        """
162        Return the total count of integers covered by at least one interval.
163      
164        Returns:
165            Count of covered integers
166        """
167        return self.tree.query(1, int(1e9))
168
169
170# Your CountIntervals object will be instantiated and called as such:
171# obj = CountIntervals()
172# obj.add(left, right)
173# param_2 = obj.count()
174
1/**
2 * Node class representing a node in the segment tree
3 * Each node maintains information about a range [l, r]
4 */
5class Node {
6    Node left;           // Left child node
7    Node right;          // Right child node
8    int rangeStart;      // Start of the range this node represents
9    int rangeEnd;        // End of the range this node represents
10    int rangeMid;        // Midpoint of the range for splitting
11    int coveredCount;    // Number of covered integers in this range
12    int lazyTag;         // Lazy propagation tag (1 if entire range should be marked as covered)
13
14    public Node(int rangeStart, int rangeEnd) {
15        this.rangeStart = rangeStart;
16        this.rangeEnd = rangeEnd;
17        this.rangeMid = (rangeStart + rangeEnd) >> 1;  // Equivalent to (rangeStart + rangeEnd) / 2
18    }
19}
20
21/**
22 * Dynamic Segment Tree implementation for range updates and queries
23 * Supports marking ranges as covered and querying total covered count
24 */
25class SegmentTree {
26    private Node root = new Node(1, (int) 1e9 + 1);  // Root covers range [1, 10^9]
27
28    public SegmentTree() {
29    }
30
31    /**
32     * Public method to mark range [left, right] as covered
33     */
34    public void modify(int left, int right, int value) {
35        modify(left, right, value, root);
36    }
37
38    /**
39     * Recursively mark range [left, right] as covered starting from given node
40     */
41    private void modify(int left, int right, int value, Node node) {
42        if (left > right) {
43            return;
44        }
45      
46        // Current node's range is completely within [left, right]
47        if (node.rangeStart >= left && node.rangeEnd <= right) {
48            // Mark entire range as covered
49            node.coveredCount = node.rangeEnd - node.rangeStart + 1;
50            node.lazyTag = value;
51            return;
52        }
53      
54        // Ensure children exist and push down lazy updates
55        pushDown(node);
56      
57        // Recursively update left subtree if needed
58        if (left <= node.rangeMid) {
59            modify(left, right, value, node.left);
60        }
61      
62        // Recursively update right subtree if needed
63        if (right > node.rangeMid) {
64            modify(left, right, value, node.right);
65        }
66      
67        // Update current node's value based on children
68        pushUp(node);
69    }
70
71    /**
72     * Public method to query covered count in range [left, right]
73     */
74    public int query(int left, int right) {
75        return query(left, right, root);
76    }
77
78    /**
79     * Recursively query covered count in range [left, right]
80     */
81    private int query(int left, int right, Node node) {
82        if (left > right) {
83            return 0;
84        }
85      
86        // Current node's range is completely within [left, right]
87        if (node.rangeStart >= left && node.rangeEnd <= right) {
88            return node.coveredCount;
89        }
90      
91        // Ensure children exist and push down lazy updates
92        pushDown(node);
93      
94        int totalCovered = 0;
95      
96        // Query left subtree if ranges overlap
97        if (left <= node.rangeMid) {
98            totalCovered += query(left, right, node.left);
99        }
100      
101        // Query right subtree if ranges overlap
102        if (right > node.rangeMid) {
103            totalCovered += query(left, right, node.right);
104        }
105      
106        return totalCovered;
107    }
108
109    /**
110     * Update parent node's value based on children's values
111     */
112    private void pushUp(Node node) {
113        node.coveredCount = node.left.coveredCount + node.right.coveredCount;
114    }
115
116    /**
117     * Push lazy updates down to children and create children if needed
118     */
119    private void pushDown(Node node) {
120        // Create left child if it doesn't exist
121        if (node.left == null) {
122            node.left = new Node(node.rangeStart, node.rangeMid);
123        }
124      
125        // Create right child if it doesn't exist
126        if (node.right == null) {
127            node.right = new Node(node.rangeMid + 1, node.rangeEnd);
128        }
129      
130        // Push down lazy tag if exists
131        if (node.lazyTag != 0) {
132            Node leftChild = node.left;
133            Node rightChild = node.right;
134          
135            // Apply lazy tag to children
136            leftChild.lazyTag = node.lazyTag;
137            rightChild.lazyTag = node.lazyTag;
138          
139            // Update children's covered counts to their full range
140            leftChild.coveredCount = leftChild.rangeEnd - leftChild.rangeStart + 1;
141            rightChild.coveredCount = rightChild.rangeEnd - rightChild.rangeStart + 1;
142          
143            // Clear current node's lazy tag
144            node.lazyTag = 0;
145        }
146    }
147}
148
149/**
150 * Main class for counting intervals
151 * Maintains a set of intervals and counts total covered integers
152 */
153class CountIntervals {
154    private SegmentTree tree = new SegmentTree();
155
156    public CountIntervals() {
157    }
158
159    /**
160     * Add interval [left, right] to the set
161     * All integers in this range become covered
162     */
163    public void add(int left, int right) {
164        tree.modify(left, right, 1);
165    }
166
167    /**
168     * Return the total count of covered integers
169     */
170    public int count() {
171        return tree.query(1, (int) 1e9);
172    }
173}
174
175/**
176 * Your CountIntervals object will be instantiated and called as such:
177 * CountIntervals obj = new CountIntervals();
178 * obj.add(left,right);
179 * int param_2 = obj.count();
180 */
181
1/**
2 * Node class for dynamic segment tree
3 * Represents a range [l, r] with lazy propagation support
4 */
5class Node {
6public:
7    Node(int left, int right)
8        : left_bound(left)
9        , right_bound(right)
10        , mid_point((left + right) / 2)
11        , covered_count(0)
12        , lazy_tag(0)
13        , left_child(nullptr)
14        , right_child(nullptr) {}
15
16    int left_bound;     // Left boundary of the range
17    int right_bound;    // Right boundary of the range
18    int mid_point;      // Middle point for splitting the range
19    int covered_count;  // Number of covered integers in this range
20    int lazy_tag;       // Lazy propagation tag (1 means fully covered, 0 means not)
21    Node* left_child;   // Pointer to left child node
22    Node* right_child;  // Pointer to right child node
23};
24
25/**
26 * Dynamic Segment Tree implementation
27 * Supports range update and range query operations
28 * Uses lazy propagation for efficiency
29 */
30class SegmentTree {
31public:
32    // Constructor initializes root with range [1, 1000000001]
33    SegmentTree()
34        : root(new Node(1, 1000000001)) {}
35
36    /**
37     * Modify (update) a range [l, r] with value v
38     * @param l: left boundary of update range
39     * @param r: right boundary of update range
40     * @param v: value to set (1 means cover the range)
41     * @param node: current node in recursion (default is root)
42     */
43    void modify(int l, int r, int v, Node* node = nullptr) {
44        if (node == nullptr) {
45            node = root;
46        }
47      
48        // Invalid range
49        if (l > r) {
50            return;
51        }
52      
53        // Current node is completely within update range
54        if (node->left_bound >= l && node->right_bound <= r) {
55            // Mark entire range as covered
56            node->covered_count = node->right_bound - node->left_bound + 1;
57            node->lazy_tag = v;
58            return;
59        }
60      
61        // Push down lazy tag before going to children
62        pushdown(node);
63      
64        // Recursively update left child if needed
65        if (l <= node->mid_point) {
66            modify(l, r, v, node->left_child);
67        }
68      
69        // Recursively update right child if needed
70        if (r > node->mid_point) {
71            modify(l, r, v, node->right_child);
72        }
73      
74        // Update current node's value based on children
75        pushup(node);
76    }
77
78    /**
79     * Query the sum in range [l, r]
80     * @param l: left boundary of query range
81     * @param r: right boundary of query range
82     * @param node: current node in recursion (default is root)
83     * @return: number of covered integers in the range
84     */
85    int query(int l, int r, Node* node = nullptr) {
86        if (node == nullptr) {
87            node = root;
88        }
89      
90        // Invalid range
91        if (l > r) {
92            return 0;
93        }
94      
95        // Current node is completely within query range
96        if (node->left_bound >= l && node->right_bound <= r) {
97            return node->covered_count;
98        }
99      
100        // Push down lazy tag before querying children
101        pushdown(node);
102      
103        int result = 0;
104      
105        // Query left child if needed
106        if (l <= node->mid_point) {
107            result += query(l, r, node->left_child);
108        }
109      
110        // Query right child if needed
111        if (r > node->mid_point) {
112            result += query(l, r, node->right_child);
113        }
114      
115        return result;
116    }
117
118private:
119    Node* root;  // Root of the segment tree
120
121    /**
122     * Push up operation: update parent based on children
123     * @param node: current node to update
124     */
125    void pushup(Node* node) {
126        node->covered_count = node->left_child->covered_count + 
127                             node->right_child->covered_count;
128    }
129
130    /**
131     * Push down operation: propagate lazy tag to children
132     * Creates children nodes dynamically if they don't exist
133     * @param node: current node whose lazy tag needs to be pushed
134     */
135    void pushdown(Node* node) {
136        // Create left child if it doesn't exist
137        if (node->left_child == nullptr) {
138            node->left_child = new Node(node->left_bound, node->mid_point);
139        }
140      
141        // Create right child if it doesn't exist
142        if (node->right_child == nullptr) {
143            node->right_child = new Node(node->mid_point + 1, node->right_bound);
144        }
145      
146        // Propagate lazy tag if exists
147        if (node->lazy_tag != 0) {
148            Node* left = node->left_child;
149            Node* right = node->right_child;
150          
151            // Apply lazy tag to children
152            left->lazy_tag = node->lazy_tag;
153            right->lazy_tag = node->lazy_tag;
154          
155            // Update children's covered count (all integers in range are covered)
156            left->covered_count = left->right_bound - left->left_bound + 1;
157            right->covered_count = right->right_bound - right->left_bound + 1;
158          
159            // Clear current node's lazy tag
160            node->lazy_tag = 0;
161        }
162    }
163};
164
165/**
166 * CountIntervals class to track covered intervals
167 * Uses segment tree to efficiently handle range updates and queries
168 */
169class CountIntervals {
170public:
171    // Constructor
172    CountIntervals() {}
173
174    /**
175     * Add an interval [left, right] to the covered set
176     * @param left: left boundary of interval
177     * @param right: right boundary of interval
178     */
179    void add(int left, int right) {
180        tree.modify(left, right, 1);
181    }
182
183    /**
184     * Count total number of unique integers covered
185     * @return: count of covered integers
186     */
187    int count() {
188        return tree.query(1, 1000000000);
189    }
190
191private:
192    SegmentTree tree;  // Internal segment tree for interval management
193};
194
195/**
196 * Your CountIntervals object will be instantiated and called as such:
197 * CountIntervals* obj = new CountIntervals();
198 * obj->add(left,right);
199 * int param_2 = obj->count();
200 */
201
1// Global variables for the interval counting tree
2let leftChild: CountIntervals | null = null;
3let rightChild: CountIntervals | null = null;
4let intervalStart: number = 0;
5let intervalEnd: number = 10 ** 9;
6let coveredSum: number = 0;
7
8// Tree node structure for interval counting
9interface CountIntervals {
10    left: CountIntervals | null;
11    right: CountIntervals | null;
12    start: number;
13    end: number;
14    sum: number;
15}
16
17// Creates a new interval tree node
18function createNode(start: number, end: number): CountIntervals {
19    return {
20        left: null,
21        right: null,
22        start: start,
23        end: end,
24        sum: 0
25    };
26}
27
28// Initialize the root node
29let root: CountIntervals = createNode(0, 10 ** 9);
30
31/**
32 * Adds an interval [left, right] to the tree and updates covered counts
33 * Uses segment tree with lazy propagation concept
34 * @param node - Current tree node
35 * @param left - Left boundary of interval to add
36 * @param right - Right boundary of interval to add
37 */
38function add(node: CountIntervals, left: number, right: number): void {
39    // If current segment is fully covered, skip processing
40    if (node.sum === node.end - node.start + 1) {
41        return;
42    }
43  
44    // If the interval completely covers current segment, mark as fully covered
45    if (left <= node.start && right >= node.end) {
46        node.sum = node.end - node.start + 1;
47        return;
48    }
49  
50    // Calculate midpoint for splitting the segment
51    const midPoint: number = (node.start + node.end) >> 1;
52  
53    // Create child nodes lazily when needed
54    if (!node.left) {
55        node.left = createNode(node.start, midPoint);
56    }
57    if (!node.right) {
58        node.right = createNode(midPoint + 1, node.end);
59    }
60  
61    // Recursively add interval to relevant child segments
62    if (left <= midPoint) {
63        add(node.left, left, right);
64    }
65    if (right > midPoint) {
66        add(node.right, left, right);
67    }
68  
69    // Update current node's sum based on children's sums
70    node.sum = node.left.sum + node.right.sum;
71}
72
73/**
74 * Returns the total count of covered integers
75 * @param node - Root node of the interval tree
76 * @returns Total number of covered integers
77 */
78function count(node: CountIntervals): number {
79    return node.sum;
80}
81
82// Wrapper functions to maintain the original interface
83function addInterval(left: number, right: number): void {
84    add(root, left, right);
85}
86
87function getCount(): number {
88    return count(root);
89}
90

Time and Space Complexity

Time Complexity:

  • For the add(left, right) operation: O(log n), where n is the range of values (in this case 10^9). The segment tree uses lazy propagation and only visits nodes along the path from root to the relevant leaf nodes, creating nodes dynamically as needed. The height of the tree is log n, so at most O(log n) nodes are visited.

  • For the count() operation: O(log n). Similar to the add operation, it traverses the tree from root to relevant nodes, with the tree height being log n.

Space Complexity:

  • The space complexity is O(m × log n), where m is the number of add operations performed and n is the data range (10^9).
  • This implementation uses a dynamic segment tree that creates nodes lazily only when needed. Each add operation may create at most O(log n) new nodes along the path from root to leaves.
  • In the worst case, after m operations, the total number of nodes created is O(m × log n).
  • Each node stores a constant amount of data (left, right, l, r, mid, v, add), so the total space is O(m × log n).

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

Common Pitfalls

1. Integer Overflow in Range Calculations

One of the most common pitfalls when implementing this segment tree is potential integer overflow when calculating the midpoint or range sizes, especially given the large range [1, 10^9].

Pitfall Example:

# Problematic code that might cause issues in some languages
mid = (l + r) // 2  # Could overflow if l + r > MAX_INT

Solution: In Python, this isn't an issue due to arbitrary precision integers, but in other languages or when porting this code, use:

mid = l + (r - l) // 2  # Safer calculation avoiding overflow

2. Off-by-One Errors in Range Boundaries

A critical pitfall is inconsistent handling of inclusive vs. exclusive ranges, particularly when splitting ranges and calculating counts.

Pitfall Example:

# Wrong: Using exclusive right boundary but calculating as inclusive
node.v = node.r - node.l  # Missing +1 for inclusive range

Solution: Always be consistent with inclusive ranges:

node.v = node.r - node.l + 1  # Correct for inclusive [l, r]

3. Forgetting to Push Down Before Operations

Failing to push down lazy updates before querying or modifying children leads to incorrect results.

Pitfall Example:

def modify(self, left, right, value, node):
    # Missing pushdown before recursive calls
    if left <= node.mid:
        self.modify(left, right, value, node.left)  # Wrong without pushdown

Solution: Always push down before accessing children:

def modify(self, left, right, value, node):
    if node.l >= left and node.r <= right:
        # Full coverage - no need to push down
        return
  
    self.pushdown(node)  # Essential before accessing children
  
    if left <= node.mid:
        self.modify(left, right, value, node.left)

4. Memory Issues with Static Segment Tree

Creating a full segment tree for range [1, 10^9] statically would require enormous memory.

Pitfall Example:

# Don't do this - would create ~2 billion nodes!
def __init__(self):
    self.tree = [Node(i, i) for i in range(1, int(1e9) + 1)]

Solution: Use dynamic segment tree that creates nodes only when needed:

def pushdown(self, node):
    # Create children only when accessed
    if node.left is None:
        node.left = Node(node.l, node.mid)
    if node.right is None:
        node.right = Node(node.mid + 1, node.r)

5. Incorrect Lazy Propagation Clear

Not clearing the lazy flag after pushing down causes values to be applied multiple times.

Pitfall Example:

def pushdown(self, node):
    if node.add != 0:
        node.left.add = node.add
        node.right.add = node.add
        # Forgot to clear: node.add = 0

Solution: Always clear the lazy flag after propagation:

def pushdown(self, node):
    if node.add != 0:
        # Apply to children
        node.left.add = node.add
        node.right.add = node.add
        # Update children values
        node.left.v = node.left.r - node.left.l + 1
        node.right.v = node.right.r - node.right.l + 1
        # Clear the flag
        node.add = 0  # Critical!

6. Pushup Without Checking Child Existence

Attempting to push up values when children might not exist in a dynamic tree.

Pitfall Example:

def pushup(self, node):
    # Dangerous if children don't exist
    node.v = node.left.v + node.right.v

Solution: The current implementation handles this by ensuring pushdown creates children before pushup is called. Alternatively, add existence checks:

def pushup(self, node):
    if node.left and node.right:
        node.v = node.left.v + node.right.v
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

How many times is a tree node visited in a depth 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