段树、区间树、二叉索引树和范围树有什么区别? [英] What are the differences between segment trees, interval trees, binary indexed trees and range trees?
本文介绍了段树、区间树、二叉索引树和范围树有什么区别?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
段树、区间树、二叉索引树和范围树的区别在于:
What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of:
- 关键思想/定义
- 应用程序
- 更高维度的性能/订单/空间消耗
请不要只给出定义.
推荐答案
所有这些数据结构都用于解决不同的问题:
All these data structures are used for solving different problems:
- 段树存储区间,并针对这些区间中的哪些区间包含给定点"查询进行了优化.
- 区间树也存储区间,但针对这些区间中的哪些区间与给定区间重叠"查询进行了优化.它也可以用于点查询——类似于线段树.
- 范围树存储点,并针对哪些点落在给定区间"查询进行了优化.
- 二叉索引树存储每个索引的项目数,并针对索引 m 和 n 之间有多少项目"查询进行了优化.
- 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.
一维的性能/空间消耗:
Performance / Space consumption for one dimension:
- 段树 - 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) 空间
- Segment tree - O(n logn) preprocessing time, O(k+logn) query time, O(n logn) space
- Interval tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
- Range tree - O(n logn) preprocessing time, O(k+logn) query time, O(n) space
- Binary Indexed tree - O(n logn) preprocessing time, O(logn) query time, O(n) space
(k 是报告结果的数量).
(k is the number of reported results).
所有数据结构都可以是动态的,因为使用场景包括数据更改和查询:
All data structures can be dynamic, in the sense that the usage scenario includes both data changes and queries:
- 段树 - 可以在 O(logn) 时间内添加/删除间隔(请参阅 此处)
- 区间树 - 可以在 O(logn) 时间内添加/删除区间
- 范围树 - 可以在 O(logn) 时间内添加/删除新点(请参阅 此处)
- 二叉索引树 - 每个索引的项目数可以在 O(logn) 时间内增加
- Segment tree - interval can be added/deleted in O(logn) time (see here)
- Interval tree - interval can be added/deleted in O(logn) time
- Range tree - new points can be added/deleted in O(logn) time (see here)
- Binary Indexed tree - the items-count per index can be increased in O(logn) time
更高的维度 (d>1):
Higher dimensions (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) 空间
- Segment tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1)) space
- Interval tree - O(n logn) preprocessing time, O(k+(logn)^d) query time, O(n logn) space
- Range tree - O(n(logn)^d) preprocessing time, O(k+(logn)^d) query time, O(n(logn)^(d-1))) space
- Binary Indexed tree - O(n(logn)^d) preprocessing time, O((logn)^d) query time, O(n(logn)^d) space
这篇关于段树、区间树、二叉索引树和范围树有什么区别?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文