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
Read full article from algorithm - What are the differences between segment trees, interval trees, binary indexed trees and range trees? - Stack Overflow
No comments:
Post a Comment