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

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