Lesson plan

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.

Back to article

Article summary

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.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.