什么是段树，区间树，二进制索引树和范围树之间的区别是什么？ [英] 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）preprocessing时间，O（K + LOGN）查询时间，为O（n LOGN）空间
• 间隔树 - 为O（n LOGN）preprocessing时间，O（K + LOGN）查询时间，O（n）的空间
• 范围树 - 为O（n LOGN）preprocessing时间，O（K + LOGN）查询时间，O（n）的空间
• 二进制索引树 - 为O（n LOGN）preprocessing时间，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）时间（见的here ）
• 间隔树 - 间隔可以添加/ O型删除（LOGN）时间
• 范围树 - 新的点可以被添加/ O型删除（LOGN）时间（见的here ）
• 二进制索引树 - 每个索引中的项目数可以在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）：

• 段树 - 为O（n（LOGN）^ D）preprocessing时间，O（K +（LOGN）^ D）查询时间，为O（n（LOGN）^（D- 1））的空间
• 间隔树 - 为O（n LOGN）preprocessing时间，O（K +（LOGN）^ D）查询时间，为O（n LOGN）空间
• 范围树 - 为O（n（LOGN）^ D）preprocessing时间，O（K +（LOGN）^ D）查询时间，为O（n（LOGN）^（D- 1）））空间
• 二进制索引树 - 为O（n（LOGN）^ D）preprocessing时间，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屋！