Segment Tree - Storage Requirements

Storage Requirements

This section analyzes the storage cost of a segment tree in a one-dimensional space.

A segment tree T on a set I of n intervals uses O(nlogn) storage.

Proof:

Lemma: Any interval of I is stored in the canonical set for at most two nodes at the same depth.

Proof: Let v₁, v₂, v₃ be the three nodes at the same depth, numbered from left to right; and let p(v) be the parent node of any given node v. Suppose is stored at v₁ and v₃. This means that spans the whole interval from the left endpoint of Int(v₁) to the right endpoint of Int(v₃). Note that all segments at a particular level are non-overlapping and ordered from left to right: this is true by construction for the level containing the leaves, and the property is not lost when moving from any level to the one above it by combining pairs of adjacent segments. Now either p(v₂) = p(v₁), or the former is to the right of the latter (edges in the tree do not cross). In the first case, Int(p(v₂))'s leftmost point is the same as Int(v₁)'s leftmost point; in the second case, Int(p(v₂))'s leftmost point is to the right of Int(p(v₁))'s rightmost point, and therefore also to the right of Int(v₁)'s rightmost point. In both cases, Int(p(v₂)) begins at or to the right of Int(v₁)'s leftmost point. Similar reasoning shows that Int(p(v₂)) ends at or to the left of Int(v₃)'s rightmost point. Int(p(v₂)) must therefore be contained in ; hence, will not be stored at v₂.

The set I has at most 4n + 1 elementary intervals. Because T is a binary balanced tree with at most 4n + 1 leaves, its height is O(logn). Since any interval is stored at most twice at a given depth of the tree, that the total amount of storage is O(nlogn).