> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Range Module Python Solution with Tests

> Tested Python solution for LeetCode 715 with 21 pytest cases. Generate a practice environment with lcpy.

LeetCode 715, [Hard](/catalog/hard). Topics: [Design](/catalog/topics/design), [Segment Tree](/catalog/topics/segment-tree), [Ordered Set](/catalog/topics/ordered-set). [View on LeetCode](https://leetcode.com/problems/range-module/description/).

Generate this problem as a practice environment: tested reference solution, 21 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 715   # by problem number
lcpy gen -s range_module   # by problem name
```

## Problem

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval `[left, right)` denotes all the real numbers `x` where `left <= x < right`.

Implement the `RangeModule` class:

* `RangeModule()` Initializes the object of the data structure.
* `void addRange(int left, int right)` Adds the half-open interval `[left, right)`, tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval `[left, right)` that are not already tracked.
* `boolean queryRange(int left, int right)` Returns `true` if every real number in the interval `[left, right)` is currently being tracked, and `false` otherwise.
* `void removeRange(int left, int right)` Stops tracking every real number currently being tracked in the half-open interval `[left, right)`.

### Examples

```
Input
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output
[null, null, null, true, false, true]

Explanation
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True, (Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False, (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
```

### Constraints

* `1 <= left < right <= 10^9`
* At most `10^4` calls will be made to `addRange`, `queryRange`, and `removeRange`.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_module/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/range_module/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from bisect import bisect_left, bisect_right


class RangeModule:
    # Time: add/remove O(n) per call, query O(log n)
    # Space: O(n) for the tracked disjoint intervals
    def __init__(self) -> None:
        # Parallel sorted arrays describing disjoint, non-adjacent half-open
        # intervals: the i-th tracked range is [starts[i], ends[i]).
        self.starts: list[int] = []
        self.ends: list[int] = []

    # Time: O(n)
    # Space: O(n)
    def add_range(self, left: int, right: int) -> None:
        # First interval whose end reaches left, and first interval that
        # starts at or after right: every interval in between overlaps and
        # must be absorbed into the merged range.
        i = bisect_left(self.ends, left)
        j = bisect_left(self.starts, right)
        if i < j:
            left = min(left, self.starts[i])
            right = max(right, self.ends[j - 1])
        self.starts[i:j] = [left]
        self.ends[i:j] = [right]

    # Time: O(log n)
    # Space: O(1)
    def query_range(self, left: int, right: int) -> bool:
        i = bisect_right(self.starts, left) - 1
        return i >= 0 and self.ends[i] >= right

    # Time: O(n)
    # Space: O(n)
    def remove_range(self, left: int, right: int) -> None:
        i = bisect_left(self.ends, left)
        j = bisect_left(self.starts, right)
        if i >= j:
            return
        kept: list[tuple[int, int]] = []
        if self.starts[i] < left:
            kept.append((self.starts[i], left))
        if self.ends[j - 1] > right:
            kept.append((right, self.ends[j - 1]))
        self.starts[i:j] = [start for start, _ in kept]
        self.ends[i:j] = [end for _, end in kept]
```

## Complexity

| Time | Space |
| - | - |
| add/remove O(n) per call, query O(log n) | O(n) for the tracked disjoint intervals |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.