A Segment Tree is basically said to be an arrangement that permits answering range queries over an array effectively, while still being flexible enough to permit modifying the array. This includes finding the sum of consecutive array elements a[l…r], or finding the minimum element during a such a variety in O(logn) time.
Between answering such queries the Segment Tree allows modifying the array by replacing one element, or maybe change the weather of an entire subsegment (e.g. assigning all elements a[l…r] to any value, or adding worth to all or any element within the subsegment).
Segment Tree may be a basically a binary tree used for storing the intervals or segments. Each node within the Segment Tree represents an interval. Consider an array A of size N and a corresponding Segment Tree
T.
- The root of T will represent the entire array A[0:N-1]
- Each leaf within the Segment Tree T will represent one element A[i] such that 0<i<N
- The internal nodes within the Segment Tree T represent the union of elementary intervals A[i:j] where 0<i<j<N
In general, a Segment Tree may be a very flexible arrangement and an enormous number of problems are often solved with it. Additionally, it’s also possible to use more complex operations and answer more complex
queries (see Advanced versions of Segment Trees). especially the Segment Tree is often easily generalised to larger dimensions. as an example with a two-dimensional Segment Tree, you’ll answer some or minimum queries over some sub rectangle of a given matrix. However only in O(log2n) time.
A critical property of Segment Trees is, that they require only a linear amount of memory. the quality Segment Tree requires ‘4n’ vertices for performing on an array of size ‘n’.
Concept of Segment Tree: As we can see here, a segment tree is a data structure used to store information from various pieces of data about array segments and answer segment queries efficiently. There are two main operations performed on a segment tree:
- range(i, j) or query: gives the sum of the array elements starting at index i and ending at index j. In this operation, we can query on an interval or segment and return the answer to the problem (say minimum/maximum/summation in the particular segment).
- update(i, val): updates the value at index i to the val in the original array and updates the segment tree accordingly. To update the element of the array A and reflect the corresponding change in the Segment Tree.
It is noted for a fact that both range/query (i, j) and update(i, val) take log(n)log(n) time, where ‘n’ is the number of elements in the Segment Tree.
Implementation / Building of a Segment Tree:
Following is the implementation of a Segment Tree. The program as we see it, the virtual code, in this case, implements the construction of segment tree for any given array. It also implements query and update operations. Complete implementation of segment tree including the query and update functions is actually just a less number of lines of code, even less than the recursive code.
Let us now understand how each of the function is working:
- The picture makes it clear that the leaf nodes are stored at i+n, so we can clearly insert all leaf nodes directly.
- The next step is to build the tree and it takes O(n) time. The parent has always it’s index less than its children so we just process all the nodes in decreasing order calculating the value of the parent node. If the code inside the build function to calculate parents seems confusing then you can see this code, it is equivalent to that inside the build function.
tree[i]=tree[2i]+tree[2i+1]
- Updating a value at any position is also simple and the time taken will be proportional to the height of the tree. We only update values in the parents of the given node which is being changed so for getting the parent, we just go up to the parent node, which is p/2 or p>>1, for node p. Here p^1 turns (2i) to (2i + 1) and vice versa to get the second child of p.
- Computing the sum also works in O(log(n)) time, if we work through an interval of [3,11).
- The idea behind the query function is that whether we should include an element in the sum or we should include its parent. Let’s look at the image once again for proper understanding.
- Consider that L is the left border of an interval and R is the right border of the interval [L, R). It is clear from the image that if L is odd then it means that it is the right child of its parent and our interval includes only L and not its parent.
- So we will simply include this node to sum and move to the parent of its next node by doing L = (L+1)/2. Now, if L is even then it is the left child of its parent and interval includes it’s parent also unless the right borders interfere. Similar conditions are applied to the right border also for faster computation. We will stop this iteration once the left and right borders meet.
- We start with a segment arr[0 . . . n-1], taking this as a sample. and every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves and for each such segment, we store the sum in the corresponding node.
- All levels of the constructed segment tree will be completely filled except the last level that is to be seen. Considering the values of the segment tree given above, we will just be building it up from the array. Also, the tree will be, as we notice the pattern, a Full Binary Tree because we always divide segments into two halves at every level. Since the constructed tree is always a full binary tree with ‘n’ leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1. Note that this does not include dummy nodes.
Just taking an example:
- Since a Segment Tree may be a binary tree, an easy linear array is often not going to represent the Segment Tree. Before building the Segment Tree, one must figure what must be stored within the Segment Tree’s node just so we get deeper into that particular topic.
- For example, if the question is to seek out the sum of all the weather in an array from indices L to R, then at each node (except leaf nodes) the sum of its children nodes is stored.
- A Segment Tree is often built using recursion (bottom-up approach). Start with the leaves and go up to the basis and update the corresponding changes within the nodes that are within the path from leaves to root. Leaves represent one element. In each step, the info of two children nodes is wont to form an indoor parent node. Each internal node will represent a union of its children’s intervals. Merging could also be different for various questions. So, recursion will find yourself at the basis node which can represent the entire array.
- For update(), search the leaf that contains the element to update. As we can see, this can be done by going to either on the left child or the right child depending on the interval which contains the element. Once the leaf is found, it is updated and again use the bottom-up approach to update the corresponding change in the path from that leaf to the root.
- To make a query(on the Segment Tree, select a range from L to R (which is usually given in the question). Recursion on the tree starting from the root and check if the interval represented by the node is completely in the range from L to R. If the interval represented by a node is completely in the range from L to R, return that node’s value.
- The Segment Tree of array A of size 7 will appear as if:
The theoretical time complexities of both previous implementation and this implementation is same but practically this is found to be much more efficient as there are no recursive calls. We simply iterate over the elements that we need. Also, this is very easy to implement.
The query for Sum of given range: Once the tree is made, the way to get the sum using the constructed segment tree. The following is the algorithm to get the sum of elements.
Update a value: Like tree construction and query operations, the update also can be done recursively. We are given an index which needs to be updated. Let diff be the value to be added. We start from the basis of the segment tree and add a difference to all or any nodes which have given index in their range. If a node
doesn’t have a given index in its range, we don’t make any changes to that node.
Time Complexities:
- Tree Construction: O( n ) – Time Complexity for tree construction is O(n). There are total 2n-1 nodes, and the value of each node is calculated just one occasion in tree construction.
- Query in Range: O( log n ) – Time complexity to query is O(Logn). To query a sum, we process at the most four nodes at every level and number of levels is O(Logn).
- Updating an element: O( log n ) – The time complexity of the update is also O(Logn). To update a leaf value, in the whole process of getting an update, we process one node at every level and number of levels is O(Logn).
So that was a brief introduction to this topic, but there is much more to discover in Data Structures and Algorithms.
To explore our courses and blogs on Data Structures, visit www.codingninjas.com.
By Deepak Jain
