段树、区间树、二叉索引树和范围树有什么区别? [英] 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屋！