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:
“To higher or lower ends, they [the majority of mankind] move too often with something of a sad countenance, with hurried and ignoble gait, becoming, unconsciously, something like thorns, in their anxiety to bear grapes; it being possible for people, in the pursuit of even great ends, to become themselves thin and impoverished in spirit and temper, thus diminishing the sum of perfection in the world, at its very sources.”
—Walter Pater (1839–1894)
“Why is it that many contemporary male thinkers, especially men of color, repudiate the imperialist legacy of Columbus but affirm dimensions of that legacy by their refusal to repudiate patriarchy?”
—bell hooks (b. c. 1955)