Segment Tree - Generalization For Higher Dimensions

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:

    Men may rise on stepping-stones
    Of their dead selves to higher things.
    Alfred Tennyson (1809–1892)

    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)