Interval Trees are trees that allow one to query on inserted ranges. For example, insert the ranges (10, 20), (15, 40) and query if there is any range that hits the value 12 or a range such as (9, 11), etc...
A Range Tree is also something similar except that the inserted entities are points and not ranges like in the interval tree.
A BIT (Binary Indexed Tree) is a notional tree that lets one compute range sums quickly. It's just a way to store sums on some subset of intervals that lets you construct the sum over any interval with these precomputed interval sum subsets. You can't use a BIT to compute range minimum or maximum queries since the only thing you can do with a BIT is compute the sum/min/max of a range that starts from index 0 (starting of the interval). For range sum in the range (a, b), one can compute the sum as sum(0, b) - sum(0, a), However, the same trick can't be used for min/max.
A Segment Tree is a more general notion of a BIT, where one precomputes the sum over a fixed set of ranges (not necessarily starting from index 0), which lets one layer O(log n) such ranges to compute the sum/min/max over any any arbitrary range.
All structures can be implemented fairly efficiently with query/update costs of O(log n), n being the number of points/ranges inserted into the structure. Of course, range reporting (not counting) queries will take longer since you need to report O(k) ranges, so the complexity goes up to Ω(k + log n) in these cases (assuming we have k ranges to report of course).
Read full article from (1) What are the major differences between segment trees, interval trees, binary indexed trees and range trees? - Quora
No comments:
Post a Comment