A tree built over an array that lets a range query, such as a sum, minimum or maximum over a contiguous span, and a single-element update both run in logarithmic time, rather than the linear time a plain array scan would need.
Facts
Core PrincipleIn computer science, the segment tree is a data structure used for storing information about intervals or segments. 1 Connections
Sources
1. Segment tree, Wikipedia
Definition section
In computer science, the segment tree is a data structure used for storing information about intervals or segments.
History section
The segment tree was invented by Jon Bentley in 1977; in 'Solutions to Klee's rectangle problems'.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.