What is a Segment Tree?
A Segment Tree is a binary tree data structure used to store intervals or segments. It lets you efficiently answer range aggregate queries (sum, min, max) and apply point or range updates on an underlying array.
While a prefix-sum array answers range sum queries in O(1), any update costs O(N) to recompute. A Segment Tree solves this by supporting both range queries and point updates in O(log N) time.
Segment Tree Structure
- Leaf Nodes: Store individual elements of the base array.
- Internal Nodes: Store the merged aggregate of their left and right children.
- Tree Size: For an array of size N, the Segment Tree needs an array of size 4N to accommodate all leaves and padding branches.
Three Core Operations
Build
O(N)
Recursively construct the tree by merging leaves up to the root.
Range Query
O(log N)
Traverse overlapping segments, accumulating the result at each matching node.
Point Update
O(log N)
Walk from the root to the target leaf, recomputing ancestor nodes on the way back.
Performance Complexity
- Tree Construction: O(N)
- Range Query Time: O(log N)
- Point Update Time: O(log N)
- Space Complexity: O(N)