| Idea: |
- store \(n\) values in the leaves of a perfect binary tree; each internal node maintains an aggregate — the minimum, maximum, or sum — of the values in its subtree
- each node thus answers the query for one canonical interval of leaves, and its aggregate is computable from its two children
- any query interval \(\langle a,b \rangle\) decomposes into \(O(\log n)\) canonical intervals, so a query combines \(O(\log n)\) stored aggregates
- changing a value only invalidates the aggregates on the path to the root, so an update recomputes \(O(\log n)\) nodes
- also known as a segment tree (the name interval tree is also used for a different structure storing a set of intervals)
|
| Advantages: |
- queries and updates both take \(O(\log n)\) time — precomputing all answers would make updates linear, storing only the values would make queries linear
- works for any associative operation (minimum, maximum, sum, greatest common divisor, …)
- simple array representation, as in a heap: children of the \(i\)-th node are at positions \(2i\) and \(2i+1\)
|
| Disadvantages: |
- the set of positions is fixed in advance — the tree aggregates values at positions, it does not maintain a dictionary of keys
- uses about twice as much memory as the values alone
|