Editing Segment tree

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 44: Line 44:
 
===Query===
 
===Query===
 
[[File:Segtree_query_92631587.png|200px|thumb|right|Only the two nodes marked in yellow must be accessed to find the minimum of the elements corresponding to the leaves marked in grey.]]
 
[[File:Segtree_query_92631587.png|200px|thumb|right|Only the two nodes marked in yellow must be accessed to find the minimum of the elements corresponding to the leaves marked in grey.]]
To ''query'' a segment tree is to use it to determine a function of a range in the underlying array (in this case, the minimum element of that range). The execution of a query is more complex than the execution of an update and will be illustrated by example. Suppose we wish to know the minimum element between the first and sixth, inclusive. We shall represent this query as <math>f(1,6)</math>. Each node in the segment tree contains the minimum in some interval: for example, the root node contains <math>f(1,8)</math>, its left child <math>f(1,4)</math>, its right <math>f(5,8)</math>, and so on, with each leaf containing <math>f(x,x)</math> for some <math>x</math>. There is no node that contains <math>f(1,6)</math>, but we notice that <math>f(1,6) = \min(f(1,4),f(5,6))</math>, and that there ''are'' nodes in the segment tree containing those two values (shown in yellow). (This expression for <math>f(1,6)</math> is not the one given by the definition of <math>f</math>, but it is fairly clear that <math>f(x,y) = \min(f(x,z),f(z+1,y))</math> where <math>x \le z < y</math>, regardless of the actual value of <math>z</math>.)<br/>
+
To ''query'' a segment tree is to use it to determine a function of a range in the underlying array (in this case, the minimum element of that range). The execution of a query is more complex than the execution of an update and will be illustrated by example. Suppose we wish to know the minimum element between the first and sixth, inclusive. We shall represent this query as <math>f(1,6)</math>. Each node in the segment tree contains the minimum in some interval: for example, the root node contains <math>f(1,8)</math>, its left child <math>f(1,4)</math>, its right <math>f(5,8)</math>, and so on, with each leaf containing <math>f(x,x)</math> for some <math>x</math>. There is no node that contains <math>f(1,6)</math>, but we notice that <math>f(1,6) = \min(f(1,4),f(5,6))</math>, and that there ''are'' nodes in the segment tree containing those two values (shown in yellow). (This expression for <math>f(1,6)</math> is not the one given by the definition of <math>f</math>, but it is fairly clear that <math>f(x,y) = \min(f(x,z),f(z+1,y))</math> where <math>x \le z \lt y</math>, regardless of the actual value of <math>z</math>.)<br/>
 
When querying a segment tree, therefore, we select a subset of the nodes with the property that the union of their sets of descendants is exactly the interval whose minimum we seek. To do so, we start at the root and recurse over nodes whose corresponding intervals have at least one element in common with the query interval. Hence, in our example of <math>f(1,6)</math>, we notice that both the left and right subtrees contain descendants that contain elements in the query interval; hence, we recurse on both. The left child of the root serves as a base case, since its interval is contained entirely within the query interval; hence it is chosen (marked in yellow). At the right child of the root, we notice that its left child has descendants in the query interval, but its right does not; hence we recurse on the former and not the latter. The former is now another base case, and it too is chosen and marked in yellow. The recursion has now terminated, and the desired minimum is the minimum of the nodes that have been chosen.
 
When querying a segment tree, therefore, we select a subset of the nodes with the property that the union of their sets of descendants is exactly the interval whose minimum we seek. To do so, we start at the root and recurse over nodes whose corresponding intervals have at least one element in common with the query interval. Hence, in our example of <math>f(1,6)</math>, we notice that both the left and right subtrees contain descendants that contain elements in the query interval; hence, we recurse on both. The left child of the root serves as a base case, since its interval is contained entirely within the query interval; hence it is chosen (marked in yellow). At the right child of the root, we notice that its left child has descendants in the query interval, but its right does not; hence we recurse on the former and not the latter. The former is now another base case, and it too is chosen and marked in yellow. The recursion has now terminated, and the desired minimum is the minimum of the nodes that have been chosen.
  

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)