Range query tree

In computer science, a Ranque Query Tree, or RQT, is a proposed term for referring to ...

tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

Applications of the segment tree are in the areas of computational geometry, and geographic information systems.

The segment tree can be generalized to higher dimension spaces as well.

Structure description

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

Storage requirements

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

Construction

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

Query

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

External links

• www.example.com