并不是说我可以在Lior的回答中添加任何东西，但它似乎可以用一个好的表格来做。

一维

K是报告结果的数量

更高的维度

D >

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

Segment tree stores intervals, and optimized for "which of these intervals contains a given point" queries. Interval tree stores intervals as well, but optimized for "which of these intervals overlap with a given interval" queries. It can also be used for point queries - similar to segment tree. Range tree stores points, and optimized for "which points fall within a given interval" queries. Binary indexed tree stores items-count per index, and optimized for "how many items are there between index m and n" queries.

一维性能/空间消耗:

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

并不是说我可以在Lior的回答中添加任何东西，但它似乎可以用一个好的表格来做。

一维

K是报告结果的数量

更高的维度

D >

段树和二叉索引树的预处理边界和空间可以改进:

段树可以存储在2n的空间中，然后使用动态规划在2n = O(n)中构建，如果您放弃在任意点上添加间隔:https://cp-algorithms.com/data_structures/segment_tree.html#toc-tgt-6 BIT可以在n中建立，看这个答案:是否可能在O(n)中建立芬威克树? BIT还支持将end追加为O(log(n))时间的操作