Segment Tree

Segment tree is a contextual binary tree designed for storing intervals or segments of a series of data items to speed up specific queries such as Range Minimum Query. Being contextual, each node of the segment tree represents an interval of data indices. Consider the following example:

An array of integers INPUT of size N, build a segment tree T which has:

1. The root of T represents the data to be queried within interval INPUT[0...N-1]

2. Leaves represent a single element INPUT[i] where 0 <= i < N.

3. The internal nodes in level h of T represents 2h number of nodes, each have data to be queried from interval from INPUT[i...j], where 0 <= i < j < N

There are N leaves in T and N - 1 internal nodes. Thus, the total number of nodes is 2 ⋅ N - 1. When the segment tree is built, its structure cannot be changed.

Figure 1. A Segment Tree Built on an Array of size 7

There are two operations that can be performed on a segment tree:

1. update: given an index and a value within the array, update the corresponding element. The time complexity is Ο(log N) time.

2. query: given index l and r, return the contextual value within the interval from l to r. (e.g. the minimal value within the range). In average, each query takes Ο(log N) time.