本文介绍了什么是段树,区间树,二进制索引树和范围树之间的区别是什么?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

什么是而言段树,区间树,二进制索引树和范围树之间的差异:

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)时间(见的)
  • 间隔树 - 间隔可以添加/ 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):

  • 段树 - 为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

这篇关于什么是段树,区间树,二进制索引树和范围树之间的区别是什么?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

07-09 18:09