Segment Tree - Query

Query

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

A query for a segment tree, receives a point qx, and retrieves a list of all the segments stored which contain the point qx.

Formally stated; given a node (subtree) v and a query point qx, the query can be done using the following algorithm:

  • Report all the intervals in I(v).
  • If v is not a leaf:
    • If qx is in Int(left child of v) then
      • Perform a query in the left child of v.
    • If qx is in Int(right child of v) then
      • Perform a query in the right child of v.

In a segment tree that contains n intervals, those containing a given query point can be reported in O(logn + k) time, where k is the number of reported intervals.

Proof: The query algorithm visits one node per level of the tree, so O(logn) nodes in total. In the other hand, at a node v, the segments in I are reported in O(1 + kv) time, where kv is the number of intervals at node v, reported. The sum of all the kv for all nodes v visited, is k, the number of reported segments.

Read more about this topic:  Segment Tree

Famous quotes containing the word query:

    “Such condition of suspended judgment indeed, in its more genial development and under felicitous culture, is but the expectation, the receptivity, of the faithful scholar, determined not to foreclose what is still a question—the “philosophic temper,” in short, for which a survival of query will be still the salt of truth, even in the most absolutely ascertained knowledge.”
    —Walter Pater (1839–1894)