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

by

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

More Related Contents:

  1. Finding all cycles in a directed graph
  2. Negative weights using Dijkstra’s Algorithm
  3. Non-recursive depth first search algorithm [closed]
  4. How to efficiently build a tree from a flat structure?
  5. What is the difference between tree depth and height?
  6. Iterating over a Binary Tree with O(1) Auxiliary Space
  7. In Order Successor in Binary Search Tree
  8. Hashing a Tree Structure
  9. reconstructing a tree from its preorder and postorder lists
  10. Why DFS and not BFS for finding cycle in graphs
  11. Why does Dijkstra’s algorithm use decrease-key?
  12. Why is depth-first search claimed to be space efficient?
  13. Algorithm to simplify a weighted directed graph of debts
  14. Print the biggest K elements in a given heap in O(K*log(K))?
  15. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  16. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  17. Iterative tree walking
  18. How do I create a URL shortener? [closed]
  19. Segmented Sieve of Eratosthenes?
  20. How do I calculate a point on a circle’s circumference?
  21. Algorithm to generate all possible permutations of a list?
  22. Find the shortest path in a graph which visits certain nodes
  23. Algorithm to separate items of the same type
  24. What’s a good algorithm to generate a maze? [closed]
  25. Array remove duplicate elements
  26. Unsupervised clustering with unknown number of clusters
  27. Quick Sort Vs Merge Sort [duplicate]
  28. Algorithm to find the maximum sum in a sequence of overlapping intervals
  29. Permute all unique enumerations of a vector in R
  30. Easiest algorithm of Voronoi diagram to implement? [closed]

Leave a Comment