段树，间隔树，二进制索引树和范围树之间有什么区别？
在以下方面，段树，间隔树，二进制索引树和范围树之间有什么区别：
- 关键思想/定义
- 应用领域
- 更高尺寸/空间消耗下的性能/订单
请不要仅仅给出定义。
回答：
所有这些数据结构用于解决不同的问题：
- 存储间隔，并针对“ 这些间隔中的哪个包含给定点 ”查询进行了优化。
- 存储间隔，但是针对“ 这些间隔中的哪些与给定间隔重叠 ”查询进行了优化。它也可以用于点查询-与段树类似。
- 存储点，并针对“ 哪些点在给定间隔内 ”查询进行了优化。
- 存储每个索引的项目数，并针对“ 在索引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）空间
以上是 段树，间隔树，二进制索引树和范围树之间有什么区别？ 的全部内容， 来源链接： utcz.com/qa/412716.html
