Constructing the segment tree
There are two important points to be noted while constructing the segment tree:
- Choosing what value to be stored in the nodes according to the problem definition
- What should the merge operation do
If the problem definition states that we need to calculate the sum over ranges, then the value at nodes should store the sum of values over the ranges.
- The child node values are merged back into the parent node to hold the value for that particular range, [i.e., the range covered by all the nodes of its subtree].
- In the end, leaf nodes store information about a single element. All the leaf nodes store the array based on which the segment tree is built.
Following are the steps for constructing a segment tree:
- Start from the leaves of the tree
- Recursively build the parents from the merge operation
The merge operation will take constant time if the operator takes constant time. SO building the whole tree takes O(N) time.
Segment tree
Contact Us