← DSA Atlas
Dedicated problem page · #715

Range Module

HardAdvanced Range Data StructuresMerge and split disjoint intervalsSorted list of disjoint intervals with binary search
Solve on LeetCode ↗
715
HardAdvanced Range Data StructuresSorted list of disjoint intervals with binary searchMerge and split disjoint intervals

Range Module

Design a data structure that tracks a set of half-open intervals [left, right) over the real numbers. Implement RangeModule with three operations: addRange(left, right) begins tracking every number in [left, right); queryRange(left, right) returns true only if every number in [left, right) is currently tracked; removeRange(left, right) stops tracking every number in [left, right).

Open official problem prompt ↗
In plain English

Maintain a set of tracked real-number ranges under additions and removals, and answer whether an arbitrary range is fully covered.

Picture it like this

Think of a highlighter on a long ruler: addRange paints a stretch (overlapping strokes fuse into one), removeRange erases a stretch (erasing the middle of a stroke leaves two shorter strokes), and queryRange asks whether a section is painted end to end with no gaps.

Example
Input
addRange(10, 20); removeRange(14, 16); queryRange(10, 14); queryRange(13, 15); queryRange(16, 17)
Output
[null, null, true, false, true]
Why
After adding [10,20) and removing [14,16), the tracked set is [10,14) plus [16,20); [10,14) is fully covered, [13,15) straddles the removed hole, and [16,17) sits inside [16,20).
Constraints
1 <= left < right <= 10^9At most 10^4 calls total to addRange, queryRange, and removeRange
Pattern lesson

See the pattern, then code

Merge and split disjoint intervals
Recognition clue

Ranges are added, removed, and queried over a huge coordinate space (up to 10^9) but with few operations, so you cannot store every integer; you maintain a compact set of disjoint intervals instead.

↗
Advanced Range Data Structures

Online prefix or range queries with updates, inversions, or coordinate compression.. Keep the tracked set as a sorted list of non-overlapping, non-adjacent half-open intervals. Adding merges everything that touches the new range into one interval; removing punches a hole, possibly splitting one interval into two; querying only needs the single interval whose start is closest to and at or before left.

New words, made simpleKnow these before the algorithm
Half-open interval [left, right)
Includes left but excludes right, so [10,14) and [14,20) meet exactly without overlapping.
Disjoint intervals
Stored intervals never overlap and are kept sorted, so each real number belongs to at most one interval.
Coordinate compression by intervals
Instead of storing 10^9 possible points, store only the O(operations) boundaries that actually matter.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Boolean array of every integer

Impossible: values go up to 10^9, far too large to allocate or scan.

Mark each covered point as tracked and scan the range on query.

Time O(range length) per callSpace O(10^9)
Best choiceSorted disjoint interval list

With at most 10^4 operations the interval count stays tiny, making this simple and fast.

Keep merged intervals sorted; merge on add, split on remove, binary-search on query.

Time O(n) add/remove, O(log n) querySpace O(n)
The rule we keep true

Invariant

The stored list is always sorted by start and contains pairwise non-overlapping half-open intervals; a real number is tracked if and only if it lies in exactly one stored interval.

Why this is correct

Reasoning

addRange absorbs every interval that overlaps or is adjacent to [left, right) into a single widened interval, so no overlaps survive; removeRange rebuilds only the surviving [start, left) and [right, end) fragments, preserving disjointness. Because intervals are disjoint and sorted, queryRange only needs the single interval whose start is the largest value not exceeding left: if that one interval covers [left, right) the range is tracked, otherwise a gap exists.

The algorithm in three movesSay these aloud before coding
1Store intervals as a list of (start, end) sorted by start, kept disjoint

intervals = [(10,20)] after addRange(10,20)

2addRange: skip intervals ending before left, merge all intervals whose start <= right by widening [left, right), then reinsert

intervals = [(10,14),(16,20)] after removeRange(14,16)

3queryRange: binary-search the last interval with start <= left and check it covers [left, right)

queryRange(16,17): candidate (16,20) covers it -> true

4removeRange: for each overlapping interval keep the [start, left) and [right, end) leftovers

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
[10,14)0
[16,20)1
1 · Readleft=10, right=20
2 · AskWhich existing intervals touch [10,20)?
3 · Update stateintervals = []
4 · ResultNo neighbors; insert (10,20). intervals = [(10,20)]
Key takeaway

State after add and remove; queryRange(16,17) is answered by the second interval [16,20).

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 8-14addRange: pass untouched left neighbors and merge

    Intervals ending before left are copied as-is; then every interval whose start is <= right is folded into the growing [left, right) window, which also merges adjacent intervals since the space is half-open.

  2. 2
    Lines 15-20addRange: place the merged interval and tail

    Append the single widened interval, then copy the remaining right-side intervals to keep the list sorted and disjoint.

  3. 3
    Lines 22-24queryRange via binary search

    bisect_right against (left, inf) finds the last interval with start <= left; the range is tracked only if that one interval also ends at or after right.

  4. 4
    Lines 26-34removeRange splits overlaps

    Intervals entirely outside [left, right) are kept; an overlapping interval contributes its [start, left) and [right, end) leftovers, which can turn one interval into two, zero, or a shortened one.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Adding a range adjacent to an existing one (end == left) must merge, not leave two intervals
  • Removing the exact middle of an interval must split it into two
  • Querying a range that spans a removed gap must return false
  • Querying when the list is empty returns false
  • Adding a range that fully contains several existing intervals collapses them into one
!

Common beginner mistakes

  • Treating intervals as closed [left, right] and mishandling the touching boundary, causing spurious overlaps or gaps
  • Forgetting adjacency merging so [10,14) and [14,20) stay separate and break a full-coverage query
  • In removeRange, appending only one leftover fragment when both [start,left) and [right,end) should survive
  • Off-by-one in the query binary search, checking the wrong candidate interval
Check your understanding

Why is it safe for queryRange to inspect only one interval instead of scanning several?

More in Advanced Range Data Structures

#218The Skyline ProblemSweep line with max-heap#307Range Sum Query – MutablePoint update, prefix-sum query#315Count of Smaller Numbers After SelfCount smaller to the right#327Count of Range SumCount prefix-sum pairs in range#493Reverse PairsCount significant inversions#699Falling SquaresRange assign, range max