Structure of the Tree
The segment tree works on the principle of divide and conquer.
- At each level, we divide the array segments into two parts. If the given array had [0, . . ., N-1] elements in it then the two parts of the array will be [0, . . ., N/2-1] and [N/2, . . ., N-1].
- We will then recursively go on until the lower and upper bounds of the range become equal.
- The structure of the segment tree looks like a binary tree.
The segment tree is generally represented using an array where the first value stores the value for the total array range and the child of the node at the ith index are at (2*i + 1) and (2*i + 2).
Contact Us