Segment tree

Common card · No. 370599

In computer science, the segment tree is a data structure used for finding the result of some associative function on a contiguous sub-array (called segment) in just O(log n) time. Commonly, the data structure is used for summation, product, maximum or minimum. A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in time O(log n + k), k being the number of retrieved intervals or segments. Applications of the segment tree are in the areas of computational geometry, geographic information systems and machine learning. The segment tree can be generalized to higher dimension spaces.

Read on Wikipedia · Image Cafce25, CC BY-SA 4.0