Question

715. Range 模块

English Version

题目描述

Range模块是跟踪数字范围的模块。设计一个数据结构来跟踪表示为 半开区间 的范围并查询它们。

半开区间 [left, right) 表示所有 left <= x < right 的实数 x 。

实现 RangeModule 类:

• RangeModule() 初始化数据结构的对象。
• void addRange(int left, int right) 添加 半开区间 [left, right)，跟踪该区间中的每个实数。添加与当前跟踪的数字部分重叠的区间时，应当添加在区间 [left, right) 中尚未跟踪的任何数字到该区间中。
• boolean queryRange(int left, int right) 只有在当前正在跟踪区间 [left, right) 中的每一个实数时，才返回 true ，否则返回 false 。
• void removeRange(int left, int right) 停止跟踪 半开区间 [left, right) 中当前正在跟踪的每个实数。

 

示例 1：

输入
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
输出
[null, null, null, true, false, true]

解释
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); 返回 true （区间 [10, 14) 中的每个数都正在被跟踪）
rangeModule.queryRange(13, 15); 返回 false（未跟踪区间 [13, 15) 中像 14, 14.03, 14.17 这样的数字）
rangeModule.queryRange(16, 17); 返回 true （尽管执行了删除操作，区间 [16, 17) 中的数字 16 仍然会被跟踪）

 

提示：

• 1 <= left < right <= 109
• 在单个测试用例中，对 addRange 、  queryRange 和 removeRange 的调用总数不超过 104 次

解法

方法一：线段树

根据题目描述，我们需要维护一个区间集合，支持区间的添加、删除和查询操作。对于区间的添加和删除操作，我们可以使用线段树来维护区间集合。

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $\log(width)$。更新某个元素的值，只需要更新 $\log(width)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

• 线段树的每个节点代表一个区间；
• 线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1,N]$；
• 线段树的每个叶子节点代表一个长度为 $1$ 的元区间 $[x,x]$；
• 对于每个内部节点 $[l,r]$，它的左儿子是 $[l,mid]$，右儿子是 $[mid+1,r]$, 其中 $mid=⌊(l+r)/2⌋$ (即向下取整)。

由于题目数据范围较大，我们可以使用动态开点的线段树来实现。动态开点的线段树是指，我们只在需要的时候才开点，而不是一开始就开好所有的点。这样可以节省空间，但是需要使用懒标记来维护区间修改。

时间复杂度方面，每次操作的时间复杂度为 $O(\log n)$。空间复杂度为 $O(m \times \log n)$。其中 $m$ 为操作次数，而 $n$ 为数据范围。

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)
 */