algorithm - 线段树、区间树、二进制索引树和范围树之间有什么区别？

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) 时间内添加/删除区间(参见 here )
• 区间树 - 可以在 O(logn) 时间内添加/删除区间
• 范围树 - 可以在 O(logn) 时间内添加/删除新点(参见 here )
• 二叉索引树 - 每个索引的项目计数可以在 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) 空间