线段树、区间树、二叉索引树和范围树之间有什么区别：
- 关键思想/定义
- 应用领域
- 更高维度的性能/秩序/空间消耗
请不要仅仅给出定义。
所有这些数据结构都用于解决不同的问题：
-
线段树存储间隔，并针对“这些区间中的哪一个包含给定点”查询。
-
区间树也存储间隔，但针对“这些间隔中哪些与给定间隔重叠" 查询。它也可以用于点查询——类似于线段树。
-
范围树存储积分，并针对“哪些点落在给定区间内”查询。
-
二叉索引树存储每个索引的项目计数，并针对“索引 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 http://3glab.cs.nthu.edu.tw/~spoon/courses/CS631100/Lecture05_handout.pdf)
-
区间树- 可以在 O(logn) 时间内添加/删除间隔
-
范围树- 可以在 O(logn) 时间内添加/删除新点（请参阅here http://www.cs.unb.ca/tech-reports/documents/TR95_100.pdf)
-
二叉索引树- 每个索引的项目计数可以在 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) 空间
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
