Implementation of Simple Segment Tree in C++ that finds a sum of a given range in a given array.
A Segment Tree is a data structure that allows us to answer Range Queries such as Range Sum, Range Maximum/Minimum, Range XOR, etc in O(logN) time complexity. It also allows us to update data in O(logN) time complexity.
Let us take an example for a clear understanding of how Segment Tree works:-
We have the array given as arr=[1,3,5,7,9,11].
Now we will construct the Segment Tree from the given array for finding the sum in a given range:-
From the above image, you can find how a Segment Tree is being constructed from the given array. We can see that the numbers written in [a,b] are the range sum from a to b inclusive and the value of the node is the sum from a to b.
From the above example, we can see that the height of a tree is log(n+1). So the total size of a Segment Tree would be (2 * 2 ceil(log(n+1))) - 1.
You can find the complete implementation of the Segment Tree in the code attached with this packet where you can also find out how to find a range sum and how to update a value in an array all in O(logN) time complexity.
Submitted by Soumak Poddar (soumakpoddar)
Download packets of source code on Coders Packet