Notes
The query that asks for all the intervals containing a given point, is often referred as stabbing query.
The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: O(nlogn) against the O(n) of the interval tree. The importance of the segment tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner.
Another advantage of the segment tree is that it can easily be adapted to counting queries; that is, to report the number of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in the canonical subsets, it can simply store the number of them. Such a segment tree uses linear storage, and requires an O(log n) query time, so it is optimal.
A version for higher dimensions of the interval tree and the priority search tree does not exist, that is, there is no clear extension of these structures that solves the analogous problem in higher dimensions. But the structures can be used as associated structure of segment trees.
Read more about this topic: Segment Tree
Famous quotes containing the word notes:
“The drama critic on your paper said my chablis-tinted hair was like a soft halo over wide set, inviting eyes, and my mouth, my mouth was a lush tunnel through which golden notes came.”
—Samuel Fuller (b. 1911)
“Poetry is either something that lives like fire inside you—like music to the musician or Marxism to the Communist—or else it is nothing, an empty formalized bore around which pedants can endlessly drone their notes and explanations.”
—F. Scott Fitzgerald (1896–1940)
“My weary limbs are scarcely stretched for repose, before red dawn peeps into my chamber window, and the birds in the whispering leaves over the roof, apprise me by their sweetest notes that another day of toil awaits me. I arise, the harness is hastily adjusted and once more I step upon the tread-mill.”
—“E. B.,” U.S. farmer. As quoted in Feminine Ingenuity, by Anne L. MacDonald (1992)