Range Query

Let us understand this with the help of the following problem

Given two integers L and R return the sum of the segment [L, R]

The first step is constructing the segment tree with the addition operator and 0 as the neutral element.

If the range is one of the node’s range values then simply return the answer.
Otherwise, we will need to traverse the left and right children of the nodes and recursively continue the process till we find a node that covers a range that totally covers a part or whole of the range [L, R]
While returning from each call, we need to merge the answers received from each of its child.

As the height of the segment tree is logN the query time will be O(logN) per query.

Range Query in Segment Tree

Introduction to Segment Trees – Data Structure and Algorithm Tutorials