Segment Tree

Definition:

Segment tree is a binary tree whose each node represents a closed interval.

The interval/segment is represented by two attributes: start and end.

Representation:

Assume we have a TreeNode A of a segment tree:

A.start: start of A's range

A.end: end of A's range

A.end is bigger or equal to A.start

Root's range: [0, n]

If A.start == A.end, A is a leaf node. Otherwise:

Left Child of A: [A.start, (A.start+A.end)/2]

Right Child of A: [(A.start+A.end)/2+1, A.end]

Properties:

Height of segment tree: ceil{log(n-1)}+1

If [i,j] is in node A, [i,j] is also in any of A's ancestors.

If [i,j] is in node A, [i,j] is not in any of A's siblings.