What are the differences between segment trees, interval trees, binary indexed trees and range trees?

algorithm tree graph-algorithm interval-tree segment-tree
Aditya picture Aditya · Jul 4, 2013 · Viewed 37.6k times · Source

What are differences between segment trees, interval trees, binary indexed trees and range trees in terms of:

  • Key idea/definition
  • Applications
  • Performance/order in higher dimensions/space consumption

Please do not just give definitions.

Answer

Lior Kogan picture Lior Kogan · Jul 6, 2013

All these data structures are used for solving different problems:

  • 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:

  • 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 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:

  • 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

Higher dimensions (d>1):

  • 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

Related questions

how can a breadth-first-search-tree include a cross-edge?

Well, I know that a breadth-first-search-tree of an undirected graph can't have a back edge. But I'm wondering how can it even have a cross-edge? I'm not able to image a spanning tree of a graph G constructed out of …

Read More
Construct a minimum spanning tree covering a specific subset of the vertices

I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V (the Steiner tree problem). I'm not limiting the size of the spanning tree to k vertices; rather …

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More