段树、间隔树、二元索引树和范围树之间有什么区别?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (32)

段树、间隔树、二元索引树和范围树在以下方面有什么区别:

  • 关键概念/定义
  • 应用
  • 高维/空间消耗的性能/顺序

请不要只给出定义。

提问于
用户回答回答于

所有这些数据结构都用于解决不同的问题:

  • 段树存储间隔,并为“这些间隔中的哪一个包含给定的点“询问。
  • 区间树存储时间间隔,但优化为“这些间隔中的哪一个与给定的间隔重叠?“询问。它也可以用于点查询-类似于段树。
  • 范围树存储点,并为“哪些点在给定的间隔内“询问。
  • 二元索引树存储项-每个索引计数,并为“索引m和n之间有多少项?“询问。

一维性能/空间消耗:

  • 段树-O(N Logn)预处理时间、O(k+logn)查询时间、O(N Logn)空间
  • 区间树-O(N Logn)预处理时间、O(k+logn)查询时间、O(N)空间
  • 范围树-O(N Logn)预处理时间、O(k+logn)查询时间、O(N)空间
  • 二元索引树-O(N Logn)预处理时间、O(Logn)查询时间、O(N)空间

所有数据结构都可以是动态的,因为使用场景既包括数据更改,也包括查询:

  • 段树-间隔可以在O(Logn)时间内添加/删除
  • 区间树-间隔可以在O(Logn)时间内添加/删除
  • 范围树-新点数可在O(Logn)时间内添加/删除
  • 二元索引树-每项指标的计数可在O(Logn)时间内增加

较高维度(d>1):

  • 段树-O(n(Logn)^d)预处理时间、O(k+(Logn)^d)查询时间、O(n(Logn)^(d-1))空间
  • 区间树-O(N Logn)预处理时间、O(k+(Logn)^d)查询时间、O(N Logn)空间
  • 范围树-O(n(Logn)^d)预处理时间,O(k+(Logn)^d)查询时间,O(n(Logn)^(d-1))空间
  • 二元索引树-O(n(Logn)^d)预处理时间、O(Logn)^d查询时间、O(n(Logn)^d)空间
用户回答回答于

扫码关注云+社区