Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Segment tree
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, the segment tree is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> used for storing information about <a href="/facts/Interval_(mathematics)/e9se3vTe">intervals</a> or segments. It allows querying which of the stored segments contain a given point. A similar data structure is the <a href="/facts/Interval_tree/hmzVk8HE">interval tree</a>. </p><p>A segment tree for a set I of <i>n</i> intervals uses <a href="/facts/Big_O_notation/weFFjSWg"><i>O</i></a>(<i>n</i> log <i>n</i>) storage and can be built in <i>O</i>(<i>n</i> log <i>n</i>) time. Segment trees support searching for all the intervals that contain a query point in time <i>O</i>(log <i>n</i> + <i>k</i>), <i>k</i> being the number of retrieved intervals or segments. </p><p>Applications of the segment tree are in the areas of <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, <a href="/facts/Geographic_information_systems/PoP1kVoa">geographic information systems</a> and <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a>. </p><p>The segment tree can be generalized to higher <a href="/facts/Dimension/0ktmUyac">dimension</a> spaces. </p>