Segment Tree - Construction

Construction

This section describes the construction of a segment tree in a one-dimensional space.

A segment tree from the set of segments I, can be built as follows. First, the endpoints of the intervals in I are sorted. The elementary intervals are obtained from that. Then, a balanced binary tree is built on the elementary intervals, and for each node v it is determined the interval Int(v) it represents. It remains to compute the canonical subsets for the nodes. To achieve this, the intervals in I are inserted one by one into the segment tree. An interval X = can be inserted in a subtree rooted at T, using the following procedure:

• If Int(T) is contained in X then store X at T, and finish.
• Else:
• If X intersects the canonical subset of the left child of T, then insert X in that child, recursively.
• If X intersects the canonical subset of the right child of T, then insert X in that child, recursively.

The complete construction operation takes O(nlogn) time, n being the number of segments in I.

Proof

Sorting the endpoints takes O(nlogn). Building a balanced binary tree from the sorted endpoints, takes linear time on n.

The insertion of an interval X = into the tree, costs O(logn).

Proof: Visiting every node takes constant time (assuming that canonical subsets are stored in a simple data structure like a linked list). When we visit node v, we either store X at v, or Int(v) contains an endpoint of X. As proved above, an interval is stored at most twice at each level of the tree. There is also at most one node at every level whose corresponding interval contains x, and one node whose interval contains x′. So, at most four nodes per level are visited. Since there are O(logn) levels, the total cost of the insertion is O(logn).