Question

715. Range Module

中文文档

Description

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.

Solutions

Solution 1: Segment Tree

According to the problem description, we need to maintain a set of intervals, supporting operations of interval addition, deletion, and query. For the addition and deletion of intervals, we can use a segment tree to maintain the set of intervals.

The segment tree divides the entire interval into multiple non-continuous sub-intervals, the number of which does not exceed $\log(width)$. To update the value of an element, only $\log(width)$ intervals need to be updated, and these intervals are all included in a large interval containing the element. When modifying the interval, we need to use lazy propagation to ensure efficiency.

• Each node of the segment tree represents an interval;
• The segment tree has a unique root node, representing the entire statistical range, such as $[1,N]$;
• Each leaf node of the segment tree represents an elementary interval of length $1$, $[x,x]$;
• For each internal node $[l,r]$, its left child is $[l,mid]$, and the right child is $[mid+1,r]$, where $mid=⌊(l+r)/2⌋$ (rounded down).

Due to the large data range of the problem, we can implement it with a dynamically allocated segment tree. A dynamically allocated segment tree means that we only allocate nodes when needed, instead of allocating all nodes at the beginning. This can save space, but it requires lazy propagation to maintain interval modification.

In terms of time complexity, the time complexity of each operation is $O(\log n)$. The space complexity is $O(m \times \log n)$. Here, $m$ is the number of operations, and $n$ is the data range.

class Node:
  __slots__ = ['left', 'right', 'add', 'v']

  def __init__(self):
    self.left = None
    self.right = None
    self.add = 0
    self.v = False


class SegmentTree:
  __slots__ = ['root']

  def __init__(self):
    self.root = Node()

  def modify(self, left, right, v, l=1, r=int(1e9), node=None):
    if node is None:
      node = self.root
    if l >= left and r <= right:
      if v == 1:
        node.add = 1
        node.v = True
      else:
        node.add = -1
        node.v = False
      return
    self.pushdown(node)
    mid = (l + r) >> 1
    if left <= mid:
      self.modify(left, right, v, l, mid, node.left)
    if right > mid:
      self.modify(left, right, v, mid + 1, r, node.right)
    self.pushup(node)

  def query(self, left, right, l=1, r=int(1e9), node=None):
    if node is None:
      node = self.root
    if l >= left and r <= right:
      return node.v
    self.pushdown(node)
    mid = (l + r) >> 1
    v = True
    if left <= mid:
      v = v and self.query(left, right, l, mid, node.left)
    if right > mid:
      v = v and self.query(left, right, mid + 1, r, node.right)
    return v

  def pushup(self, node):
    node.v = bool(node.left and node.left.v and node.right and node.right.v)

  def pushdown(self, node):
    if node.left is None:
      node.left = Node()
    if node.right is None:
      node.right = Node()
    if node.add:
      node.left.add = node.right.add = node.add
      node.left.v = node.add == 1
      node.right.v = node.add == 1
      node.add = 0


class RangeModule:
  def __init__(self):
    self.tree = SegmentTree()

  def addRange(self, left: int, right: int) -> None:
    self.tree.modify(left, right - 1, 1)

  def queryRange(self, left: int, right: int) -> bool:
    return self.tree.query(left, right - 1)

  def removeRange(self, left: int, right: int) -> None:
    self.tree.modify(left, right - 1, -1)


# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

class Node {
  Node left;
  Node right;
  int add;
  boolean v;
}

class SegmentTree {
  private Node root = new Node();

  public SegmentTree() {
  }

  public void modify(int left, int right, int v) {
    modify(left, right, v, 1, (int) 1e9, root);
  }

  public void modify(int left, int right, int v, int l, int r, Node node) {
    if (l >= left && r <= right) {
      node.v = v == 1;
      node.add = v;
      return;
    }
    pushdown(node);
    int mid = (l + r) >> 1;
    if (left <= mid) {
      modify(left, right, v, l, mid, node.left);
    }
    if (right > mid) {
      modify(left, right, v, mid + 1, r, node.right);
    }
    pushup(node);
  }

  public boolean query(int left, int right) {
    return query(left, right, 1, (int) 1e9, root);
  }

  public boolean query(int left, int right, int l, int r, Node node) {
    if (l >= left && r <= right) {
      return node.v;
    }
    pushdown(node);
    int mid = (l + r) >> 1;
    boolean v = true;
    if (left <= mid) {
      v = v && query(left, right, l, mid, node.left);
    }
    if (right > mid) {
      v = v && query(left, right, mid + 1, r, node.right);
    }
    return v;
  }

  public void pushup(Node node) {
    node.v = node.left != null && node.left.v && node.right != null && node.right.v;
  }

  public void pushdown(Node node) {
    if (node.left == null) {
      node.left = new Node();
    }
    if (node.right == null) {
      node.right = new Node();
    }
    if (node.add != 0) {
      node.left.add = node.add;
      node.right.add = node.add;
      node.left.v = node.add == 1;
      node.right.v = node.add == 1;
      node.add = 0;
    }
  }
}

class RangeModule {
  private SegmentTree tree = new SegmentTree();

  public RangeModule() {
  }

  public void addRange(int left, int right) {
    tree.modify(left, right - 1, 1);
  }

  public boolean queryRange(int left, int right) {
    return tree.query(left, right - 1);
  }

  public void removeRange(int left, int right) {
    tree.modify(left, right - 1, -1);
  }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */

template <class T>
class CachedObj {
public:
  void* operator new(size_t s) {
    if (!head) {
      T* a = new T[SIZE];
      for (size_t i = 0; i < SIZE; ++i)
        add(a + i);
    }
    T* p = head;
    head = head->CachedObj<T>::next;
    return p;
  }
  void operator delete(void* p, size_t) {
    if (p) add(static_cast<T*>(p));
  }
  virtual ~CachedObj() {}

protected:
  T* next;

private:
  static T* head;
  static const size_t SIZE;
  static void add(T* p) {
    p->CachedObj<T>::next = head;
    head = p;
  }
};
template <class T>
T* CachedObj<T>::head = 0;
template <class T>
const size_t CachedObj<T>::SIZE = 10000;
class Node : public CachedObj<Node> {
public:
  Node* left;
  Node* right;
  int add;
  bool v;
};

class SegmentTree {
private:
  Node* root;

public:
  SegmentTree() {
    root = new Node();
  }

  void modify(int left, int right, int v) {
    modify(left, right, v, 1, 1e9, root);
  }

  void modify(int left, int right, int v, int l, int r, Node* node) {
    if (l >= left && r <= right) {
      node->v = v == 1;
      node->add = v;
      return;
    }
    pushdown(node);
    int mid = (l + r) >> 1;
    if (left <= mid) modify(left, right, v, l, mid, node->left);
    if (right > mid) modify(left, right, v, mid + 1, r, node->right);
    pushup(node);
  }

  bool query(int left, int right) {
    return query(left, right, 1, 1e9, root);
  }

  bool query(int left, int right, int l, int r, Node* node) {
    if (l >= left && r <= right) return node->v;
    pushdown(node);
    int mid = (l + r) >> 1;
    bool v = true;
    if (left <= mid) v = v && query(left, right, l, mid, node->left);
    if (right > mid) v = v && query(left, right, mid + 1, r, node->right);
    return v;
  }

  void pushup(Node* node) {
    node->v = node->left && node->left->v && node->right && node->right->v;
  }

  void pushdown(Node* node) {
    if (!node->left) node->left = new Node();
    if (!node->right) node->right = new Node();
    if (node->add) {
      node->left->add = node->right->add = node->add;
      node->left->v = node->right->v = node->add == 1;
      node->add = 0;
    }
  }
};

class RangeModule {
public:
  SegmentTree* tree;

  RangeModule() {
    tree = new SegmentTree();
  }

  void addRange(int left, int right) {
    tree->modify(left, right - 1, 1);
  }

  bool queryRange(int left, int right) {
    return tree->query(left, right - 1);
  }

  void removeRange(int left, int right) {
    tree->modify(left, right - 1, -1);
  }
};

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule* obj = new RangeModule();
 * obj->addRange(left,right);
 * bool param_2 = obj->queryRange(left,right);
 * obj->removeRange(left,right);
 */

const N int = 1e9

type node struct {
  lch   *node
  rch   *node
  added bool
  lazy  int
}

type segmentTree struct {
  root *node
}

func newSegmentTree() *segmentTree {
  return &segmentTree{
    root: new(node),
  }
}

func (t *segmentTree) update(n *node, l, r, i, j, x int) {
  if l >= i && r <= j {
    n.added = x == 1
    n.lazy = x
    return
  }
  t.pushdown(n)
  m := int(uint(l+r) >> 1)
  if i <= m {
    t.update(n.lch, l, m, i, j, x)
  }
  if j > m {
    t.update(n.rch, m+1, r, i, j, x)
  }
  t.pushup(n)
}

func (t *segmentTree) query(n *node, l, r, i, j int) bool {
  if l >= i && r <= j {
    return n.added
  }
  t.pushdown(n)
  v := true
  m := int(uint(l+r) >> 1)
  if i <= m {
    v = v && t.query(n.lch, l, m, i, j)
  }
  if j > m {
    v = v && t.query(n.rch, m+1, r, i, j)
  }
  return v
}

func (t *segmentTree) pushup(n *node) {
  n.added = n.lch.added && n.rch.added
}

func (t *segmentTree) pushdown(n *node) {
  if n.lch == nil {
    n.lch = new(node)
  }
  if n.rch == nil {
    n.rch = new(node)
  }
  if n.lazy != 0 {
    n.lch.added = n.lazy == 1
    n.rch.added = n.lazy == 1
    n.lch.lazy = n.lazy
    n.rch.lazy = n.lazy
    n.lazy = 0
  }
}

type RangeModule struct {
  t *segmentTree
}

func Constructor() RangeModule {
  return RangeModule{
    t: newSegmentTree(),
  }
}

func (this *RangeModule) AddRange(left int, right int) {
  this.t.update(this.t.root, 1, N, left, right-1, 1)
}

func (this *RangeModule) QueryRange(left int, right int) bool {
  return this.t.query(this.t.root, 1, N, left, right-1)
}

func (this *RangeModule) RemoveRange(left int, right int) {
  this.t.update(this.t.root, 1, N, left, right-1, -1)
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddRange(left,right);
 * param_2 := obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */

class Node {
  left: Node | null;
  right: Node | null;
  add: number;
  v: boolean;

  constructor() {
    this.left = null;
    this.right = null;
    this.add = 0;
    this.v = false;
  }
}

class SegmentTree {
  private root: Node;

  constructor() {
    this.root = new Node();
  }

  modify(
    left: number,
    right: number,
    v: number,
    l: number = 1,
    r: number = 1e9,
    node: Node | null = null,
  ): void {
    if (node === null) {
      node = this.root;
    }

    if (l >= left && r <= right) {
      node.v = v === 1;
      node.add = v;
      return;
    }

    this.pushdown(node);

    const mid = (l + r) >> 1;

    if (left <= mid) {
      this.modify(left, right, v, l, mid, node.left);
    }

    if (right > mid) {
      this.modify(left, right, v, mid + 1, r, node.right);
    }

    this.pushup(node);
  }

  query(
    left: number,
    right: number,
    l: number = 1,
    r: number = 1e9,
    node: Node | null = null,
  ): boolean {
    if (node === null) {
      node = this.root;
    }

    if (l >= left && r <= right) {
      return node.v;
    }

    this.pushdown(node);

    const mid = (l + r) >> 1;
    let result = true;

    if (left <= mid) {
      result = result && this.query(left, right, l, mid, node.left);
    }

    if (right > mid) {
      result = result && this.query(left, right, mid + 1, r, node.right);
    }

    return result;
  }

  pushup(node: Node): void {
    node.v = !!(node.left && node.left.v && node.right && node.right.v);
  }

  pushdown(node: Node): void {
    if (node.left === null) {
      node.left = new Node();
    }

    if (node.right === null) {
      node.right = new Node();
    }

    if (node.add !== 0) {
      node.left.add = node.add;
      node.right.add = node.add;
      node.left.v = node.add === 1;
      node.right.v = node.add === 1;
      node.add = 0;
    }
  }
}

class RangeModule {
  private tree: SegmentTree;

  constructor() {
    this.tree = new SegmentTree();
  }

  addRange(left: number, right: number): void {
    this.tree.modify(left, right - 1, 1);
  }

  queryRange(left: number, right: number): boolean {
    return this.tree.query(left, right - 1);
  }

  removeRange(left: number, right: number): void {
    this.tree.modify(left, right - 1, -1);
  }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * var obj = new RangeModule()
 * obj.addRange(left,right)
 * var param_2 = obj.queryRange(left,right)
 * obj.removeRange(left,right)
 */