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

段树，区间树，二叉索引树和范围树之间的区别是：

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

请不要只给定义。

Answer 1

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

• 段树存储间隔，并针对“ 这些间隔中包含给定点的哪个 ”查询进行了优化。
• 间隔树也会存储间隔，但会针对“ 哪些间隔与给定间隔重叠 ”查询进行优化。 它也可以用于点查询 – 类似于分段树。
• 范围树存储点，并针对“ 哪些点位于给定间隔内 ”查询进行了优化。
• 二进制索引树存储每个索引的项目数，并针对“ 索引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）空间

Answer 2

不是我可以给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 |