Segment Tree
Visualize how segment trees enable efficient range queries and point updates in logarithmic time.
Segment Tree
Concept Overview
A Segment Tree is a versatile binary tree data structure used for storing aggregated information about subarrays (intervals) of an array. It supports efficient range aggregate queries (such as range sum, minimum, or maximum) and point updates over an array, both in logarithmic time. This makes it highly efficient for scenarios with dynamic data where frequent updates and range queries are required.
Mathematical Definition
Given an array A of size n, a segment tree T is built such that the root represents the entire array A[0...n-1]. Each internal node represents the merging of its two children. The height of the tree is O(log n), and it requires O(n) memory.
Maximum number of nodes: 2h+1 - 1 ≈ 4n
For a node representing interval [L, R]:
Midpoint: M = ⌊(L + R) / 2⌋
Left child: [L, M]
Right child: [M + 1, R]
Query/Update Time Complexity: O(log n)
Space Complexity: O(n)
Key Concepts
- Building the Tree: The tree is built recursively bottom-up. Leaf nodes store single array elements. Internal nodes store the combined result (e.g., sum) of their children. This process takes O(n) time.
- Range Queries: To answer a query for an interval [l, r], the tree is traversed. If a node's interval is completely within [l, r], its value is returned. If it's partially inside, the query splits to both children. If it's outside, a neutral value (like 0 for sum) is returned.
- Point Updates: To update A[i], the leaf node representing A[i] is updated, and the change is propagated back up to the root, updating all ancestral nodes. This takes O(log n) time.
- Lazy Propagation: An optimization for range updates (e.g., adding a value to all elements in [l, r]). Updates are deferred to children only when those children are accessed, reducing range update time from O(n) to O(log n).
Historical Context
The Segment Tree was originally introduced in computational geometry in the late 1970s by Jon Bentley to solve problems related to orthogonal intervals, such as finding intersecting line segments. Over time, its application expanded significantly into competitive programming and general computer science as a standard tool for handling dynamic range queries efficiently.
Real-world Applications
- Computational Geometry: Used in algorithms to report intersections of rectangles and line segments efficiently.
- Financial Systems: Useful for calculating dynamic rolling minimums, maximums, or sums in stock price data over time intervals.
- Game Development: Applicable in dynamic spatial queries and collision detection.
Related Concepts
- Binary Search Tree — A fundamental tree structure for point-based operations, conceptually similar but functionally distinct.
- Fenwick Tree (Binary Indexed Tree) — A simpler, more space-efficient alternative for prefix sum and point updates.
- Prefix Sums — A static array technique that achieves O(1) range sum queries but O(n) point updates.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Segment Tree module.
Try Segment Tree on Riano →