Range query tree

In computer science, a Range Query Tree, or RQT, is a term for referring to a data structure that is used for performing range queries and updates on an underlying array, which is treated as the leaves of the tree. RQTs are, in principle, complete binary trees with a static structure, where each node stores the result of applying a fixed binary operation to a range of the tree's leaves (or elements of the underlying array).

A Range Query Tree uses O(n) storage, where n is the size of the array on top of which the structure is built, and can be constructed in O(n) time. Range Query Trees support performing range queries and updates on its leaves in O(log n) time.

Range Query Trees are usually wrongly referred to as Segment Trees or Range Trees, both of them inaccurate terms since they also refer to other already existing structures.

Range Query Trees can be generalized to higher dimension spaces, and can also be implemented with two Fenwick Trees when the range operations are sums.

Structure description

A Range Query Tree is a complete binary tree that has a static structure, meaning that its content can be changed but not its size. The values of the underlying array over which the associative operation needs to be performed are stored in the leaves of the tree and the number of values have to be padded to the next power of two with the identity value for the associative operation used.

Each node of the tree represents an interval of the underlying array of values. The root node represents the whole padded length of the array and each of its two children represent the first and second half of the interval respectively. The nodes in the tree are generated recursively in this manner until they represent one single element in the underlying array.

Storage requirements

A Range Query Tree with an underlying array of size n (padded to a power of two) has n leaves and a total of 2log2 n +1 nodes which requires O(n) storage requirement.

References

[1] [2] [3]

  1. ^ "Advanced Tutorial I: Range Queries - UBC Sport Programming Team". sites.google.com.
  2. ^ D.S. Hirschberg; D.J. Volper. "IMPROVED UPDATE/QUERY ALGORITHMS FOR THE INTERVAL VALUATION PROBLEM" (PDF). Ics.uici.edu. Retrieved 2017-06-01.
  3. ^ Ahsan, Arefin, Md; Sarwar, Uddin, Md Yusuf; Indranil, Gupta; Klara, Nahrstedt (2009). "Q-Tree: A Multi-Attribute Based Range Query Solution for Tele-immersive Framework". 2009 29th IEEE International Conference on Distributed Computing Systems.{{cite journal}}: CS1 maint: multiple names: authors list (link)

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.