The motivation
Suppose you must answer many range questions on an array, like the sum or minimum over a slice, while also updating elements. A plain array makes one of those operations slow. A segment tree balances both so each runs in logarithmic time.
The structure
A segment tree is a binary tree built over the array.
- The root covers the entire array.
- Each internal node splits its range into a left half and a right half.
- The leaves correspond to single elements.
Every node stores an aggregate of its range, such as the sum or the minimum of the elements beneath it. A node value is computed by combining its two children.
Building
You build bottom up. Leaves take the raw array values, and each parent combines its children. Because the tree is balanced and has about twice as many nodes as the array length, it fits comfortably in a flat array indexed by node number.
What it buys you
With ranges stored hierarchically, any query touches only a handful of nodes whose ranges tile the asked slice, and any single update only refreshes the nodes along one root to leaf path.
Key idea
A segment tree stores aggregates of nested array ranges so both range queries and point updates stay logarithmic.