问段树、区间树、二进制索引树和范围树有什么不同？

EN

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

• Segment树存储间隔，并针对“这些间隔中的哪些包含给定点”进行了优化。queries.
• Interval树也存储了间隔，但针对“这些间隔中的哪些与给定的间隔重叠”查询进行了优化。它也可以用于点查询-类似于段树。
• Range树存储点数，并针对“哪些点落在给定间隔内”进行了优化。queries.
• Binary索引树存储每个索引的项数，并针对“索引m和n之间有多少项”查询进行了优化。

一个维度的性能/空间消耗：

• Segment树- O(k+logn)预处理时间，O(k+logn)查询时间，O(k+logn)
  • Segment树-O(k+logn)预处理时间，O(logn)查询时间，O(n) space
  • Range树-O(k+logn)预处理时间，O(k+logn)查询时间，O(n) space
  • Range索引树-O(k+logn)预处理时间，O( logn)查询时间，O(n)

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

所有数据结构都可以是动态的，因为使用场景包括数据更改和查询：

• Segment树计数-间隔可以在O(logn)时间内添加/删除(请参阅here)
• Interval树-间隔可以在O(logn)时间内添加/删除)
  • Segment树-新点可以在O(logn)时间内添加/删除(请参阅索引树-每个索引的项数可以在O(logn)时间内增加

更高维度(d>1)：

• Segment树- O(n( logn) ^d)预处理时间，O(k+( logn) ^d)查询时间，O(n(logn)^(d-1)) space
• Range树- O(n Logn)预处理时间，O(k+(logn)^d)查询时间，O(n Logn)space
• Range树k+- O(n(logn)^d)预处理时间，O(k+(logn)^d)查询时间，O(n(Logn)^(d-1) space
• Binary索引树- O(n(logn)^d)预处理时间，O((logn)^d)查询时间，O(n(logn)^d) space
• Binary

可以改进分段树和二进制索引树的预处理和空间的界限：

• 段树可以存储在2n空间中，随后可以使用动态编程在2n = O(n)中构建，如果您放弃在任何任意点添加间隔：https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6
• BIT可以在O(log(n))中构建，请参阅以下答案：Is it possible to build a Fenwick tree in O(n)?
• BIT还支持在2n = O(n) time

中作为操作追加到末尾