golang刷leetcode：统计区间中的整数数目

给你区间的 空 集，请你设计并实现满足要求的数据结构：

新增：添加一个区间到这个区间集合中。

统计：计算出现在 至少一个 区间中的整数个数。

实现 CountIntervals 类：

CountIntervals() 使用区间的空集初始化对象

void add(int left, int right) 添加区间 [left, right] 到区间集合之中。

int count() 返回出现在 至少一个 区间中的整数个数。

注意：区间 [left, right] 表示满足 left <= x <= right 的所有整数 x 。

示例 1：

输入

["CountIntervals", "add", "add", "count", "add", "count"]

[[], [2, 3], [7, 10], [], [5, 8], []]

输出

[null, null, null, 6, null, 8]

解释

CountIntervals countIntervals = new CountIntervals(); // 用一个区间空集初始化对象

countIntervals.add(2, 3); // 将 [2, 3] 添加到区间集合中

countIntervals.add(7, 10); // 将 [7, 10] 添加到区间集合中

countIntervals.count(); // 返回 6

// 整数 2 和 3 出现在区间 [2, 3] 中

// 整数 7、8、9、10 出现在区间 [7, 10] 中

countIntervals.add(5, 8); // 将 [5, 8] 添加到区间集合中

countIntervals.count(); // 返回 8

// 整数 2 和 3 出现在区间 [2, 3] 中

// 整数 5 和 6 出现在区间 [5, 8] 中

// 整数 7 和 8 出现在区间 [5, 8] 和区间 [7, 10] 中

// 整数 9 和 10 出现在区间 [7, 10] 中

提示：

1 <= left <= right <= 109

最多调用 add 和 count 方法 总计 105 次

调用 count 方法至少一次

解题思路：

1，本题用到了线段树，思想是通过二分法求区间的点的个数

2，对于插入的点如果在当前区间内，不用重复求了

3，如果比当前区间大，是线段树不允许出现的情况

4，因此可以在mid将区间划分成两部分

5，递归求解左右区间

type Node struct {
  l, r, val, lv, rv int
  lo, ro            *Node
}

func (o *Node) update(l, r int) {
    fmt.Println(l,r,o.l,o.r)
  if o.r-o.l+1 == o.val {
    return
  }
  if l <= o.l && o.r <= r {
    o.val = o.r - o.l + 1
    return
  }
  m := (o.l + o.r) >> 1
  if l <= m {
    if o.lo == nil {
      o.lo = &Node{l: o.l, r: m}
    }
    o.lo.update(l, r)
    o.lv = o.lo.val
  }
  if r > m {
    if o.ro == nil {
      o.ro = &Node{l: m + 1, r: o.r}
    }
    o.ro.update(l, r)
    o.rv = o.ro.val
  }
  o.val = o.lv + o.rv
}

const N = int(1e9)

type CountIntervals struct {
  root *Node
}

func Constructor() CountIntervals {
  root := &Node{
    l: 1,
    r: N,
  }
  return CountIntervals{
    root: root,
  }
}

func (this *CountIntervals) Add(left int, right int) {
  this.root.update(left, right)
}

func (this *CountIntervals) Count() int {
  return this.root.val
}

复制