Segment Tree implementation in C++

By Soumak Poddar

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.