Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

• Difficulty: HARD
• Problem: Range Module
• Topics: Design, Segment Tree, Ordered Set

Problem gist

A range module remembers which real-number intervals are currently being tracked. It must support three operations on half-open ranges [left, right):

• add every point in a range to the tracked set;
• remove every point in a range from the tracked set;
• report whether every point in a range is tracked.

The half-open convention matters: adjacent ranges such as [5, 8) and [8, 12) fit together without overlapping, while removing [8, 10) leaves the first range untouched. Operations may overlap in any order, so the data structure must combine additions, preserve removals, and answer queries against the latest state.

Deriving the implicit segment tree

The coordinates extend up to 10^9, which makes an array with one entry per unit interval impossible. However, every operation boundary is an integer. That means a tree can represent the elementary intervals [1, 2), [2, 3), and so on without losing information: an update to [left, right) becomes an inclusive update over the cells from left through right - 1.

Start with one root representing the entire coordinate domain. Each node stores whether its whole segment is covered. A second field, pending, is a lazy assignment:

• True means the entire segment is covered;
• False means the entire segment is uncovered;
• None means the segment is mixed and its children contain the details.

An addition or removal that fully contains a node’s segment can assign that node immediately. Its descendants are discarded because the new assignment replaces every older decision below it. For a partial overlap, the node is split into two children, its uniform state is copied down, and the update follows only the necessary branches. Afterward, equal uniform children can be merged back into their parent.

A query follows the same decomposition. If it reaches a uniform node, that one Boolean answers the query for any subrange inside the node. If it reaches a mixed node, every intersected child must be covered. The tree creates nodes only along boundaries touched by updates, so the huge unused coordinate space consumes no memory.

For coordinate bound U, each operation takes O(log U) time. Here the height is only about 30 because U = 10^9. After m operations, the worst-case space usage is O(m log U), although merging uniform subtrees often releases nodes.

Python solution

The implementation keeps the public method names required by LeetCode and isolates tree maintenance in small helpers. It also validates the interval contract at the API boundary, while the recursive work stays bounded by the tree height.

from dataclasses import dataclass
from typing import Optional


DOMAIN_START = 1
DOMAIN_END = 10**9 - 1  # Represents the final unit interval [10**9 - 1, 10**9).


@dataclass(slots=True)
class _RangeNode:
    """One segment in an implicit lazy-propagation tree."""

    covered: bool = False
    pending: Optional[bool] = False
    left: Optional["_RangeNode"] = None
    right: Optional["_RangeNode"] = None


class RangeModule:
    """Track, untrack, and query half-open ranges of real numbers."""

    def __init__(self) -> None:
        self._root = _RangeNode()

    def addRange(self, left: int, right: int) -> None:
        """Track every point in [left, right)."""
        self._validate_interval(left, right)
        self._assign(
            self._root,
            DOMAIN_START,
            DOMAIN_END,
            left,
            right - 1,
            covered=True,
        )

    def queryRange(self, left: int, right: int) -> bool:
        """Return whether every point in [left, right) is tracked."""
        self._validate_interval(left, right)
        return self._query(
            self._root,
            DOMAIN_START,
            DOMAIN_END,
            left,
            right - 1,
        )

    def removeRange(self, left: int, right: int) -> None:
        """Stop tracking every point in [left, right)."""
        self._validate_interval(left, right)
        self._assign(
            self._root,
            DOMAIN_START,
            DOMAIN_END,
            left,
            right - 1,
            covered=False,
        )

    @staticmethod
    def _validate_interval(left: int, right: int) -> None:
        if not DOMAIN_START <= left < right <= DOMAIN_END + 1:
            raise ValueError("Expected 1 <= left < right <= 10**9")

    @staticmethod
    def _set_uniform(node: _RangeNode, covered: bool) -> None:
        """Replace a node's entire segment with one coverage state."""
        node.covered = covered
        node.pending = covered
        node.left = None
        node.right = None

    @staticmethod
    def _split(node: _RangeNode) -> None:
        """Materialize children that inherit a uniform parent's state."""
        if node.pending is None:
            # Mixed nodes have already been split.
            assert node.left is not None and node.right is not None
            return

        inherited_state = node.pending
        node.left = _RangeNode(
            covered=inherited_state,
            pending=inherited_state,
        )
        node.right = _RangeNode(
            covered=inherited_state,
            pending=inherited_state,
        )
        node.pending = None

    @staticmethod
    def _merge_if_uniform(node: _RangeNode) -> None:
        """Recompute a parent and collapse equal uniform children."""
        assert node.left is not None and node.right is not None
        node.covered = node.left.covered and node.right.covered

        children_are_same_uniform_state = (
            node.left.pending is not None
            and node.left.pending == node.right.pending
        )
        if children_are_same_uniform_state:
            node.pending = node.left.pending
            node.left = None
            node.right = None

    def _assign(
        self,
        node: _RangeNode,
        segment_left: int,
        segment_right: int,
        query_left: int,
        query_right: int,
        covered: bool,
    ) -> None:
        if query_left <= segment_left and segment_right <= query_right:
            self._set_uniform(node, covered)
            return

        self._split(node)
        assert node.left is not None and node.right is not None

        midpoint = segment_left + (segment_right - segment_left) // 2
        if query_left <= midpoint:
            self._assign(
                node.left,
                segment_left,
                midpoint,
                query_left,
                query_right,
                covered,
            )
        if query_right > midpoint:
            self._assign(
                node.right,
                midpoint + 1,
                segment_right,
                query_left,
                query_right,
                covered,
            )

        self._merge_if_uniform(node)

    def _query(
        self,
        node: _RangeNode,
        segment_left: int,
        segment_right: int,
        query_left: int,
        query_right: int,
    ) -> bool:
        if (
            query_left <= segment_left and segment_right <= query_right
        ) or node.pending is not None:
            # A uniform node answers any subrange contained inside it.
            return node.covered

        assert node.left is not None and node.right is not None
        midpoint = segment_left + (segment_right - segment_left) // 2

        if query_right <= midpoint:
            return self._query(
                node.left,
                segment_left,
                midpoint,
                query_left,
                query_right,
            )
        if query_left > midpoint:
            return self._query(
                node.right,
                midpoint + 1,
                segment_right,
                query_left,
                query_right,
            )

        return self._query(
            node.left,
            segment_left,
            midpoint,
            query_left,
            query_right,
        ) and self._query(
            node.right,
            midpoint + 1,
            segment_right,
            query_left,
            query_right,
        )

Interview follow-ups

Could this be implemented with a sorted list of disjoint intervals?

Yes. Keep non-overlapping tracked intervals sorted by their left endpoint. Adding a range finds the first overlapping or adjacent interval, merges every interval it touches, and replaces that slice with one combined interval. Removing a range finds the overlaps and preserves at most a left remainder and a right remainder. A query binary-searches for the interval whose start is immediately before left and checks whether its end reaches right.

This representation is often shorter and uses O(n) space for n stored intervals. Queries take O(log n), but an update can touch or shift O(n) list entries. It is a strong practical choice when the number of intervals is small; the implicit segment tree gives more predictable logarithmic worst-case updates.

What if all operation endpoints are known before processing begins?

Collect and sort every distinct endpoint, then coordinate-compress the gaps between consecutive endpoints. A conventional lazy segment tree can operate on those compressed elementary intervals. This works because coverage can change only at an endpoint that appears in some operation.

With k distinct endpoints, preprocessing costs O(k log k), each operation costs O(log k), and the tree uses O(k) space. The tradeoff is that the method is offline: a newly arriving endpoint cannot be represented without rebuilding or using a dynamic structure.

How would the module report the total tracked length?

Add covered_length to each node. A uniform covered node stores the length of its represented coordinate segment, an uncovered node stores zero, and a mixed node stores the sum of its children. Lazy assignments update this aggregate immediately, so the root always contains the total tracked length.

Additions and removals remain O(log U), and reading the total becomes O(1). The main implementation omits this field because Boolean range queries need only the covered invariant.

How could a query return the uncovered gaps inside a range?

Traverse only nodes that intersect the requested range. Skip uniform covered nodes, emit the intersection of uniform uncovered nodes, and recurse through mixed nodes. Adjacent emitted pieces should be merged before returning them so tree boundaries do not leak into the API.

The traversal costs O(log U + g log U) in a straightforward implementation for g reported gaps, with output size imposing an unavoidable O(g) lower bound. A sorted-interval representation can make this operation especially natural when gap reporting is common.

What changes if overlapping clients need reference counts?

A Boolean assignment is no longer sufficient: removing one client’s range must not erase coverage contributed by another client. Store a lazy integer delta and the minimum coverage count within each segment. An addition applies +1, a removal applies -1, and a range is fully tracked exactly when its minimum count is positive.

Lazy range-add and range-min operations still take O(log U). The caller must either identify clients or guarantee balanced removals; otherwise counts can become negative and no longer describe meaningful ownership.

How would concurrency affect the design?

The current tree mutates several nodes during one operation, so an unsynchronized query could observe a partially applied update. The simplest correct design protects the module with a reader-writer lock: additions and removals take the write lock, while independent queries share the read lock.

That preserves the same algorithmic complexity but serializes updates. If read throughput dominates, a persistent segment tree can build a new root for each update and then atomically publish it; readers use immutable snapshots without locks, at the cost of retaining O(log U) new nodes per update until old versions are released.

Why are the ranges half-open rather than closed?

Half-open intervals make adjacency and length unambiguous: [left, right) has length right - left, and [a, b) joins [b, c) without double-counting b. Removal boundaries also compose cleanly because removing [b, c) does not alter any point strictly before b.

The tree uses inclusive integer cell indices only as an internal representation. Converting [left, right) to [left, right - 1] preserves the public semantics because each leaf represents one real interval [x, x + 1).

Takeaway

The key observation is that a billion possible coordinates do not require a billion stored entries. An implicit segment tree materializes only the boundaries that updates reach, while lazy assignment lets a whole covered or uncovered region collapse into one node. The result is a range module whose additions, removals, and all-points queries each take logarithmic time with a small, fixed tree height.