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:
“‘Tis the gift to be simple ‘tis the gift to be free
‘Tis the gift to come down where you ought to be
And when we find ourselves in the place just right
‘Twill be in the valley of love and delight.”
—Unknown. ‘Tis the Gift to Be Simple.
AH. American Hymns Old and New, Vols. I–II. Vol. I, with music; Vol. II, notes on the hymns and biographies of the authors and composers. Albert Christ-Janer, Charles W. Hughes, and Carleton Sprague Smith, eds. (1980)
“Of all the horrid, hideous notes of woe,
Sadder than owl-songs or the midnight blast,
Is that portentous phrase, “I told you so,”
Uttered by friends, those prophets of the past.”
—George Gordon Noel Byron (1788–1824)
“Lap me in soft Lydian airs,
Married to immortal verse,
Such as the meeting soul may pierce
In notes with many a winding bout
Of linked sweetness long drawn out,
With wanton heed and giddy cunning,
The melting voice through mazes running,
Untwisting all the chains that tie
The hidden soul of harmony;”
—John Milton (1608–1674)