{x}
blog image

Range Module

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).

 

Example 1:

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 <= 109
  • At most 104 calls will be made to addRange, queryRange, and removeRange.

Solution Explanation: Range Module

This problem requires designing a data structure to efficiently track ranges of numbers and perform operations like adding, removing, and querying ranges. A segment tree is an ideal choice for this due to its logarithmic time complexity for these operations.

Approach:

We use a segment tree to represent the ranges. Each node in the tree corresponds to a range of numbers. The leaves represent individual numbers, and internal nodes represent ranges composed of their children's ranges. Each node stores a boolean value v indicating whether the entire range it represents is covered and an integer add for lazy propagation. Lazy propagation is crucial for efficiency in updating large ranges.

Data Structures:

  • Node: Represents a node in the segment tree. It stores:

    • left: Pointer to the left child node.
    • right: Pointer to the right child node.
    • add: Integer representing the lazy update value (1 for add, -1 for remove, 0 for no update).
    • v: Boolean indicating whether the entire range is covered (true) or not (false).

  • SegmentTree: Manages the segment tree:

    • root: Root node of the segment tree.
    • modify(): Updates a range in the segment tree.
    • query(): Checks if a range is fully covered.
    • pushup(): Updates a node's v value based on its children's values.
    • pushdown(): Propagates lazy updates down the tree.

  • RangeModule: The main class implementing the range module functionalities:

    • tree: Instance of SegmentTree.
    • addRange(): Adds a range using SegmentTree.modify().
    • queryRange(): Queries a range using SegmentTree.query().
    • removeRange(): Removes a range using SegmentTree.modify().

Algorithm:

  1. addRange(left, right): Calls SegmentTree.modify() to mark the range [left, right) as covered (add = 1).

  2. queryRange(left, right): Calls SegmentTree.query() to check if the range [left, right) is fully covered.

  3. removeRange(left, right): Calls SegmentTree.modify() to mark the range [left, right) as uncovered (add = -1).

Segment Tree Operations:

  • modify(left, right, v): Recursively traverses the segment tree. If a node's range is fully contained within [left, right), it updates the node's add and v accordingly. Otherwise, it recursively updates the relevant children after propagating lazy updates (pushdown). Finally, it updates the current node's v using pushup.

  • query(left, right): Recursively checks if the entire range [left, right) is covered. If a node's range is fully contained within [left, right), it returns the node's v. Otherwise, it recursively queries the relevant children after propagating lazy updates.

  • pushup(node): Updates the v value of a node based on its children's v values. v is true only if both children's v are true.

  • pushdown(node): Propagates the add value down to the children. If a node has a non-zero add value, it updates its children's add and v values and resets its own add to 0.

Time Complexity:

All operations (addRange, queryRange, removeRange) have a time complexity of O(log n), where n is the range of numbers (109 in this case). This is because the segment tree's height is logarithmic in the range size.

Space Complexity:

The space complexity is O(m log n), where m is the number of operations performed and n is the range of numbers. This is because the segment tree's size can grow up to m log n nodes in the worst case. The dynamically allocated segment tree optimizes space usage compared to a statically allocated one, but the space complexity remains logarithmic.

The provided code demonstrates the implementation in Python, Java, C++, Go, and TypeScript, showcasing the core logic of using a segment tree with lazy propagation to solve the Range Module problem efficiently. Each language version follows the same basic structure and algorithmic approach.