We need to maintain a dynamic collection of non-overlapping intervals and support three operations: adding a range (merging it with any overlapping intervals), removing a range (splitting intervals if necessary), and querying whether a range is fully covered.

The difficult part is handling the merging and splitting correctly. When we add [10, 20) and then remove [14, 16), our collection becomes {[10, 14), [16, 20)}. If we then add [13, 18), we need to merge it with the existing pieces to get {[10, 20)} again.

The value range goes up to 10^9, so we can't use a boolean array indexed by value: a billion-entry array is too large. We need to store intervals and detect overlap without touching every integer in a range. The number of operations is at most 10^4, which leaves room for approaches that are O(n) per operation, as long as they stay correct under merging and splitting.

Key Constraints:

Intuition

Maintain a list of non-overlapping intervals sorted by start position. For each operation, scan the list to find which intervals overlap the given range, then merge, split, or check as needed.

The invariant is that the intervals are always sorted by start and never overlap. As long as addRange and removeRange rebuild the list to preserve that property, queryRange can decide coverage by finding a single interval that contains the query: if any interval starts at or before left and ends at or after right, the range is fully tracked. No two intervals can ever combine to cover a range, because a gap between them means some value is untracked.

Algorithm

For addRange(left, right):

For queryRange(left, right):

For removeRange(left, right):

Example Walkthrough

Code

This approach scans every interval on every operation. Since the intervals are sorted, binary search can jump directly to the relevant ones instead of starting from the front.

Intuition

The intervals are already sorted and non-overlapping, so a linear scan repeats work that binary search avoids. A TreeMap (or equivalent sorted map) keyed by interval start lets us jump directly to the interval that matters in O(log n).

For a range [left, right), the only interval that can overlap its left edge is the one whose start is the largest value at or before left. A TreeMap's floorKey operation returns exactly that key in O(log n), which replaces the front-to-back scan of the brute force.

Algorithm

For addRange(left, right):

For queryRange(left, right):

For removeRange(left, right):

Example Walkthrough

Code

The TreeMap gives O(log n) queries, but add and remove can still cost O(n) when a single call merges or splits many intervals. A segment tree bounds every operation by the depth of the tree instead.

Intuition

A segment tree supports range updates and range queries in O(log n). The obstacle here is that the value range goes up to 10^9, so building a full tree over every coordinate upfront would allocate billions of nodes. A dynamic segment tree (also called an implicit segment tree) avoids that by creating a node only when an operation first touches its subrange.

The tree covers [1, 10^9). Each node represents a subrange and stores whether that entire subrange is tracked. An update marks a range as tracked or untracked and uses lazy propagation to defer pushing the change to children until a later operation visits them. A query reports whether every part of the query range is tracked.

Each operation visits at most O(log C) nodes, where C = 10^9 is the size of the coordinate space. Since log2(10^9) is about 30, an operation touches at most around 30 levels regardless of how many intervals exist.

Algorithm

Example Walkthrough

Code