Range query tree
In computer science, a Ranque Query Tree, or RQT, is a proposed 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. RQT are, in principle, perfect binary trees with a static structure, where each node stores information about a binary operation applied to a range of the tree's leaves.
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 query and update queries on the underlying array in O(log n) time, where a range query is an operation such as returning the sum of all the elements of the array in a given range, and a range update is an operation such as adding a certain number to all the elements in a given range of the array.
Range Query Trees are usually referred to as Segment Tree or Range Tree, both of them inaccurate names since they may also refer to other already existing structures.
Range Query Trees can be generalized to higher dimension spaces as well, and can also be implemented with two Fenwick Trees when the range operations are sums.
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.
Update
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.