Segment Tree
Subject: Computer and Technology noun /ˈsɛɡ.mənt ˌtriː/ 1 definition
- data-structures
- tree-algorithms
- range-queries
- computer-science
-
Definition (noun)
Entry #276 · UpdatedA Segment Tree is a binary tree data structure that recursively partitions an array's index range into halves down to single-element leaf nodes. Each internal node stores an associative aggregate—such as a sum, minimum, maximum, or greatest common divisor—computed by merging the values of its left and right child intervals during an O(n) build. Because any contiguous query interval
[l, r]decomposes into O(log n) canonical tree nodes and updating a single element affects only its ancestors along one root-to-leaf path, both range queries and point updates execute in O(log n) time using O(n) space. Unlike static prefix-sum arrays or Fenwick trees that rely on invertible operations for arbitrary[l, r]queries, a Segment Tree handles dynamic updates for any associative operation at the cost of higher memory overhead and constant factors.Common Types
Iterative (Bottom-Up) Segment Tree: Maps the tree into a flat
2n-element array and traverses upward from leaf indices without recursion, lowering constant-factor overhead and memory footprint for point updates and range queries.Lazy Propagation Segment Tree: Stores deferred update tags at internal nodes and pushes pending modifications down to children only when visited, enabling O(log n) range updates alongside range queries.
Persistent Segment Tree: Allocates only O(log n) new nodes along the modified root-to-leaf path on each update while sharing unchanged subtrees, enabling historical version queries and k-th order statistics over subarrays.
Dynamic (Sparse) Segment Tree: Allocates child nodes on demand using pointers rather than a preallocated array, supporting updates and queries over vast coordinate ranges
[0, U](such as10^9) in O(log U) time per operation without coordinate compression.
Example
A telemetry service tracks peak request latency per 1-second bucket across an 86,400-second day inside an iterative Segment Tree backed by a 172,800-slot
max-aggregate array. When a late metric updates bucket41,200and an alert evaluates the maximum latency across[39,600, 43,200), the engine recalculates 17 nodes along the root-to-leaf path and resolves the 3,600-bucket window in fewer than 35 array lookups.