This data structure is the latest cool thing that I got really excited about. I was working on my solution for Codility challenge Chromium 2017, which I managed to solve it with 100 out of 100 score (little bit more about this in my next post), and I needed refreshing of my basic algorithm/data structures knowledge because I haven’t done this kind of problem solving in past 10 years, since my college days.
Many problems can be solved with this data structure in a more optimal way than you could think of before. For example, it can be used in situations when
- range update in array is needed,
- finding a sum of elements in a range,
- finding min/max in a range etc.
Before I proceed on how this data structure works I would like to mention the complexities on which we can achieve these actions. First, the complexity to build this tree is O(N), the complexity of range update would be O(logN), the complexity of query(range) operation is also O(logN).
Construction of Segment Tree from Array
Let’s take an example of a simple array and let’s say we need to work with the sums of the sub arrays. To use this technique we need to create two segment trees, in the first we’ll keep the segments sums and in the other we’ll keep (if any) the update and update the first one only when if we need some of the updated segments/values. We’ll call the first one SegmentTree and the second one where we keep the updates LazyTree. For the visualization of the segment tree I’m using VisuAlgo tool, which is a very cool and free to use tool if you want to have better understanding on how some algorithms work.
Let’s take this array as an example:
array = [92, 12, 83, 91, 4, 48, 47, 8]
from this array we are constructing this segment tree in which we are keeping the sums of the segments from which we can later fast calculate the sum any sub array.
For example if we want to get the sum of all elements in the range [0,4] all we need to do is sum the nodes [0,3] and [4,4], which are the first nodes from left and right of the node that completely fall under the wanted range.
As we mentioned we need to create a LazyTree in which we’ll keep the potential updates and later propagate them to the SegmentTree when we need to use them. Because we still don’t have any pending updates the initial state will look like this.
Updating a range in array (query update)
For the range update process we’ll use the LazyTree to keep the update data and later update smaller segments if needed. Let’s take the example from above and add 10 to all elements in the range [0,4]. Again, starting from the root we need to find all segments that fully overlap with the wanted segment, in this case [0,4].
In classic segment tree we would need to go and update all the nodes from a certain range until we reach the leaf nodes, but with lazy propagation we update only the segment nodes that fully overlap (and all above them) and in the LazyTree we’ll keep the update in their child nodes (if any). So, after the update the SegmentTree will have the following values
You can notice that updated nodes are [0,3] and [4,4] and all nodes that are going towards the root. Also, nodes that are “bellow” [0,3] are not updated although they are fully in range also.
The updates for those nodes will be kept in the LazyTree child nodes of [0,3] ([0,1] and [2,3])and porpagated into the SegmentTree (or child nodes) only if needed.
C# implementation and working example
I made an implementation of this Segment Tree with Lazy Propagation in C#, you can check out/modify/use that code from my GitHub repository: https://github.com/jordfocus/LazyPropagationSegmentTree
It’s a full working example in Visual Studio project, if you have some comments/suggestions or just question regarding this implementation please let me know.