Range query tree

Short description: Tree-based data structure

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 2^{log₂ n} +1 nodes which requires O(n) storage requirement.