Generalization For Higher Dimensions
The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimension versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses O(nlogd-1n) storage, and answers queries in O(logdn).
The use of fractional cascading lowers the query time bound by a logarithmic factor. The use of the interval tree on the deepest level of associated structures lowers the storage bound with a logarithmic factor.
Read more about this topic: Segment Tree
Famous quotes containing the words higher and/or dimensions:
“I never feel so conscious of my race as I do when I stand before a class of twenty-five young men and women eager to learn about what it is to be black in America.”
—Claire Oberon Garcia, African American college professor. As quoted in the Chronicle of Higher Education, p. B3 (July 27, 1994)
“The truth is that a Pigmy and a Patagonian, a Mouse and a Mammoth, derive their dimensions from the same nutritive juices.... [A]ll the manna of heaven would never raise the Mouse to the bulk of the Mammoth.”
—Thomas Jefferson (1743–1826)