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

Question

在以下方面,段树,间隔树,二进制索引树和范围树之间有什么区别:

• 关键思想/定义
• 应用
• 更高维度/空间消耗的性能/订单

请不要只给出定义.

Answer 1

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

• 段树存储间隔,并针对" 这些间隔中的哪一个包含给定点 "查询进行了优化.
• 间隔树也存储间隔,但针对" 这些间隔中的哪一个与给定间隔重叠 "查询进行了优化.它也可以用于点查询 - 类似于段树.
• 范围树存储点,并针对" 哪些点落在给定间隔内 "查询进行了优化.
• 二进制索引树存储每个索引的项目计数,并针对" 索引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)空间

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

在使用场景包括数据更改和查询的意义上,所有数据结构都可以是动态的:

• 段树 - 可以在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)空间

Answer 2

并不是说我可以为Lior的答案添加任何东西,但似乎它可以用一张好桌子.

一维

k 是报告结果的数量

|              | Segment       | Interval   | Range          | Indexed   |
|--------------|--------------:|-----------:|---------------:|----------:|
|Preprocessing |        n logn |     n logn |         n logn |    n logn |
|Query         |        k+logn |     k+logn |         k+logn |      logn |
|Space         |        n logn |          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 |

这些表是在Github格式化Markdown中创建的 - 如果需要图像,请参阅Gist.