段树,区间树,二叉索引树和范围树之间有什么区别?

段树,区间树,二叉索引树和范围树之间的区别是:

  • 主要观点/定义
  • 应用
  • 性能/订单更高维度/空间消耗

请不要只给定义。

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

  • 段树存储间隔,并针对“ 这些间隔中包含给定点的哪个 ”查询进行了优化。
  • 间隔树也会存储间隔,但会针对“ 哪些间隔与给定间隔重叠 ”查询进行优化。 它也可以用于点查询 – 类似于分段树。
  • 范围树存储点,并针对“ 哪些点位于给定间隔内 ”查询进行了优化。
  • 二进制索引树存储每个索引的项目数,并针对“ 索引m和n之间有多less项目 ”查询进行了优化。

一维性能/空间消耗:

  • 分段树 – 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)空间

(k是报告结果的数量)。

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

  • 段树 – 间隔可以在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)空间
  • (n(logn)^ d)预处理时间,O(k +(logn)^ d)查询时间,O(n(logn)^(d-1)))空间
  • 二进制索引树 – O(n(logn)^ d)预处理时间,O((logn)^ d)查询时间,O(n(logn)^ d)空间

不是我可以给Lior的答案添加任何东西,但似乎可以做一个好桌子。

这些在Github格式化Markdown中创build表格 – 参见Gist 。

一维

k是报告结果的数量

  | Segment | Interval | Range | Indexed | --------------|--------------:|-----------:|---------------:|----------:| Preprocessing | n logn | n logn | n logn | n logn | Query | k+logn | k+logn | k+logn | logn | Space | n | n | n | n | | | | | | Insert/Delete | logn | logn | logn | logn | 

在这里输入图像说明

更高的尺寸

d > 1

  | Segment | Interval | Range | Indexed | --------------|--------------:|-----------:|---------------:|----------:| Preprocessing | n(logn)^d | n logn | n(logn)^d | n(logn)^d | Query | k+(logn)^d | k+(logn)^d | k+(logn)^d | (logn)^d | Space | n(logn)^(d-1) | n logn | n(logn)^(d-1)) | n(logn)^d | 

在这里输入图像说明

Interesting Posts