Range queries fast
A segment tree answers range queries, such as the sum or minimum over a subarray, and supports point updates, both in logarithmic time. It is a binary tree where each node covers a contiguous segment of the array and stores an aggregate of that segment.
Building the tree
We build recursively. The root covers the whole array. Each internal node splits its range in half, giving a left child and a right child. A leaf covers a single element. After both children are built, a node combines their stored values with the chosen operation. Building visits each node once, so it is linear in the array size.
Querying and updating
- Query a range by descending from the root. If a node's segment lies fully inside the query, return its stored value. If it is disjoint, return the operation's identity. Otherwise recurse into both children and combine.
- Update a single index by walking down to its leaf, changing it, and recombining values back up the path to the root.
A common layout stores the tree in a flat array of size about four times the input, so no pointers are needed.
Key idea
Each node stores the aggregate of a range, so any query or point update touches only a logarithmic number of nodes along root to leaf paths.