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

219
votes

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.

3
algorithmtreegraph-algorithminterval-treesegment-tree
It is not a duplicate, That question is if fenwick trees is generalization of interval tress, and my question is more specific and different. – Aditya
It has not been answered at stackoverflow.com/questions/2795989/…, the answer there just gives definition. – Aditya
How is it too broad? "What are some differences between x and y?" is as clear and focused as it gets. This is a very good question. – IVlad
And there is no good answer for this available anywhere. A good answer will be great for the community – Aditya
Most of these data structures (except Fenwick trees) are reviewed in this pdf: "Interval, Segment, Range, and Priority Search Trees" (by D. T. Lee). Or you can read it as a chapter from this book: "Handbook of Data Structures and Applications". – Evgeny Kluev

3 Answers

350
votes

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
28
votes

Not that I can add anything to Lior's answer, but it seems like it could do with a good table.

One Dimension

k is the number of reported results

Operation Segment Interval Range Indexed
Preprocessing n logn n logn n logn n logn
Query k+logn k+logn k+logn logn
Space n logn n n n
Insert/Delete logn logn logn logn

Higher Dimensions

d > 1

Operation Segment Interval Range Indexed
Preprocessing n(logn)^d n logn n(logn)^d n(logn)^d
Query k+(logn)^d k+(logn)^d k+(logn)^d (logn)^d
Space n(logn)^(d-1) n logn n(logn)^(d-1)) n(logn)^d
0
votes

The bounds for preprocessing and space for segment trees and binary indexed trees can be improved: