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, perfect 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.
A Range Query Tree is a perfect 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.
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.
- "Advanced Tutorial I: Range Queries - UBC Sport Programming Team". sites.google.com.
- D.S. Hirschberg; D.J. Volper. "IMPROVED UPDATE/QUERY ALGORITHMS FOR THE INTERVAL VALUATION PROBLEM" (PDF). Ics.uici.edu. Retrieved 2017-06-01.
- Ahsan, Arefin, Md; Sarwar, Uddin, Md Yusuf; Indranil, Gupta; Klara, Nahrstedt. "Q-Tree: A Multi-Attribute Based Range Query Solution for Tele-immersive Framework". 2009 29th IEEE International Conference on Distributed Computing Systems.