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:
“But there are higher secrets of culture, which are not for the apprentices, but for proficients. These are lessons only for the brave. We must know our friends under ugly masks. The calamities are our friends.”
—Ralph Waldo Emerson (1803–1882)
“Words are finite organs of the infinite mind. They cannot cover the dimensions of what is in truth. They break, chop, and impoverish it.”
—Ralph Waldo Emerson (1803–1882)