Forgot Password ?
New password will be sent to following email id
Sorted Segment Tree
( Introduction )
Segment tree is a highly versatile data structure, based upon the divide-and-conquer paradigm, which can be thought of as a tree of intervals of an underlying array, constructed so that queries on ranges of the array as well as modifications to the array's elements may be efficiently performed. <br><br> A segment trees has following three operations: <br> <ul> <li><b>Building tree:</b> To initialize the tree segments or intervals values</li> <li><b>Update tree:</b> To update value of an interval or segment</li> <li><b>Query tree:</b> To retrieve the value of an interval or segment</li> </ul> <h4><u> Structure </u></h4> <ul> <li> It is a binary tree in which each node stores value corresponding to a range of some array. </li> <li> Each node is associated with an interval of array and contains the value(s) of one or more functions applied to that range. (functions may be like minimum, maximum, sum, etc) </li> <li> Root node is associated to entire array. (i.e. it stores value of function(s) for all elements present in an array)</li> <li> Each leaf node is associated with a single element of an array.</li> <li> Each non leaf node has two children associated to it and is split into approximately two equal half. </li> <li> If a non leaf node is associated to a range <b> L ... R </b> than its left child's range will be <b> L ... ⌊(L+R)/2⌋ </b> and its right child's range will be <b> ⌊(L+R)/2⌋+1 ... R</b>.</li> </ul> <img src='https://s5.postimg.org/t180wxpzr/Segment_Tree.jpg' style='width:80%;height:80%' alt='Image Not Found'></img> <h4><u> Building tree </u></h4> Once we know what is needed to be stored in segment tree, it can be created using recursive (bottom-up) approach. Value of a node is calculated by first calculating values of its children and then merging them to find value of current node. <h4><u> Update tree </u></h4> For update we need to search for the leaf that is needed to be updated which can be found by going into left child or right child of the current node. Once leaf node is found it will be updated and bottom-up approach will be used to update the change in the path from leaf to root. <h4><u> Query tree </u></h4> We will be given a range <b>L ... R</b> for which we need to find the value(s) of functions used in problem. We will traverse tree starting from root. Check if the given range of node completely lies within <b>L ... R</b> then return this node's value. If the given node completely lies outside the range then return suitable values which depends upon function used in problem. Or else query on both child nodes of the current node and merge their answer. <h4><u> Space Complexity </u></h4> Root node is associated with an interval of <b>N</b> elements. In each we divide the interval into two equal half so depth of segment tree will be <b>⌈ log<sub>2</sub> N ⌉</b>. A binary tree with depth of <b>⌈ log<sub>2</sub> N ⌉</b> may have <b>2<sup>⌈ log<sub>2</sub> N ⌉+1</sup>-1</b> nodes. So some mathematical analysis shows that a segment tree on an array of <b>N</b> elements requires an array of no more than <b>4N</b> elements for its own storage.Asymptotically, a segment tree uses <b>O(N)</b> space. <h4><u> TimeComplexity </u></h4> <ul> <li> Construction requires a constant number of operations on each node of the segment tree and there are <b>O(N)</b> nodes hence construction takes linear time. </li> <li> Constant number of operations are performed on each node present in path from leaf to root and number of nodes will be equal to height of tree. Hence updation takes <b>O(log<sub>2</sub> N)</b>.</li> <li>Mathematical analysis shows that there are atmost 2 nodes which are expanded at each level. Since there are <b>log<sub>2</sub> N</b> levels hence query takes <b>O(log<sub>2</sub> N)</b>.</li> </ul>