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.

Lemma: Any interval of I is stored in the canonical set for at most two nodes at the same depth.
Proof: Let v1, v2, v3 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 v1 and v3. This means that spans the whole interval from the left endpoint of Int(v1) to the right endpoint of Int(v3). 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(v2) = p(v1), or the former is to the right of the latter (edges in the tree do not cross). In the first case, Int(p(v2))'s leftmost point is the same as Int(v1)'s leftmost point; in the second case, Int(p(v2))'s leftmost point is to the right of Int(p(v1))'s rightmost point, and therefore also to the right of Int(v1)'s rightmost point. In both cases, Int(p(v2)) begins at or to the right of Int(v1)'s leftmost point. Similar reasoning shows that Int(p(v2)) ends at or to the left of Int(v3)'s rightmost point. Int(p(v2)) must therefore be contained in ; hence, will not be stored at v2.
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).

Read more about this topic:  Segment Tree

Other articles related to "requirements, storage requirements":

Integrated Logistics Support - Packaging, Handling, Storage, and Transportation (PHS&T)
... transported, and stored properly for short- and long-term requirements ... equipment and packaging, handling and storage requirements, and pre-positioning of material and parts ... It also includes preservation and packaging level requirements and storage requirements (for example, sensitive, proprietary, and controlled items) ...

Famous quotes containing the word storage:

    Many of our houses, both public and private, with their almost innumerable apartments, their huge halls and their cellars for the storage of wines and other munitions of peace, appear to me extravagantly large for their inhabitants. They are so vast and magnificent that the latter seem to be only vermin which infest them.
    Henry David Thoreau (1817–1862)