What it solves
You have an array and a stream of two kinds of operations: change a single element, and ask for an aggregate, such as the sum or minimum, over an arbitrary range. A plain array makes one operation fast and the other slow. A segment tree makes both fast.
The structure
Picture a binary tree where the leaves are the array elements. Each internal node covers the union of its children's ranges and stores the aggregate of that whole range. The root covers the entire array.
- A point update walks from the leaf up to the root, refreshing each ancestor's stored aggregate.
- A range query descends from the root, taking whole nodes that lie fully inside the asked range and recursing only where the range cuts across a node.
Why queries are fast
Any query range is covered by a small number of complete nodes spread across the tree's levels. Because the tree's height is small, both updates and queries touch only a few nodes per level, giving logarithmic cost.
The aggregate can be any associative operation: sum, minimum, maximum, greatest common divisor, and more. This flexibility makes the segment tree a workhorse for range problems.
Key idea
Store range aggregates in a balanced tree so point updates climb to the root and range queries assemble from a few complete nodes.