Skip to main content
Definition Website Computer and Technology

Segment Tree

Subject: Computer and Technology noun /ˈsɛɡ.mənt ˌtriː/ 1 definition

  1. Definition (noun)

    Entry #276 · Updated

    A 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 as 10^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 bucket 41,200 and 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.